Invited Speaker---Assoc. Prof. Yong Wang


Renewable Energy School, North China Electric Power University, China

Biography: Yong Wang works as an associate professor on Combinatorial Optimization, Applied Mathematics at the North China Electric Power University, Beijing. He obtained his Ph.D. degree on manufacturing engineering of aeronautics and astronautic in Beihang University, Beijing, China and the master degree on vehicle engineering in Beihang University, Beijing, China, and he got the bachelor degree on manufacturing engineering of aircraft in Nanjing University of Aeronautic and Astronautics, Nanjing, China. Before he joined the North China Electric Power University, he focused on the Assembly Sequence Planning (ASP) and Assembly Unit Partition. The ASP is one combinatorial optimization problem and the second subject is a multi-attribute (multi-objective) decision problem. In recent years, he devoted to the possible algorithms for TSP. He proposed the frequency graphs as a new way to reduce the TSP on complete graph to a TSP on a sparse graph so as to reduce its complexity. From February 2, 2015 to March 2, 2016, he studied the frequency graph for TSP at the Department of Mathematics of University of California, San Diego. There he discovered the frequency quadrilaterals with Professor Jeffrey B. Remmel together, which gave the theoretical basis of frequency graphs for TSP. There are several interesting problems that he is working on. His recent interests include Combinatorial Optimization, Graph algorithms, Applied Probability and Fuzzy Mathematics and their applications in industrial engineering.

Speech Title: A random algorithm to compute a sparse graph for TSP based on frequency quadrilaterals
Abstract: We study the symmetric traveling salesman problem via frequency graphs which is computed with frequency quadrilaterals. According to the frequency quadrilaterals, we give a probability model that shows the frequency of edges in the optimal Hamiltonian cycle is bigger than the average frequency of all of edges. Moreover, when we choose N frequency quadrilaterals containing an edge e to compute its frequency, the frequency of e in the optimal Hamiltonian cycle approaches 5N as n is big enough. Based on the theories, we present a random algorithm to compute a sparse graph for traveling salesman problem. The algorithm needs O(n^2) computation time. The experimental results show we obtain a sparse graph with O(nlg(n)) edges for general TSP instances.