A new multi-level algorithm for balanced partition problem on large scale directed graphs

Graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering etc.In this paper,we study the partition problem on large scale directed graphs under a new objective function,a new instance of graph partition problem.We firstly propose the modeling of this problem,then design an algorithm based on multi-level strategy and recursive partition method,and finally do a lot of simulation experiments.The experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as METIS.In addition,our algorithm is better than METIS on unbalanced ratio.

New Meta-Heuristic for Combinatorial Optimization Problems：Intersection Based Scaling

Combinatorial optimization problems are found in many application fields such as computer science, engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms. Keywords combinatorial optimization - TSP (Traveling Salesman Problem) - GPP (Graph Partitioning Problem) - IBS (Intersection-Based Scaling) - meta heuristic Regular PaperThis work is supported by the National Basic Research 973 Program of China (Grant No.TG1998030401).Peng Zou was born in 1979. He received the B.S. degree in computer software from University of Science and Technology of China (USTC) in 2000. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include algorithms for NP-hard problems and parallel computing.Zhi Zhou was born in 1976. He received the B.S. degree in computer software from USTC in 1995. Now he is a Ph.D. candidate in computer science of USTC. His current research interests include combinatorial problem and parallel computing.Ying-Yu Wan was born in 1976. He received the B.S. degree in computer software from USTC in 1997, and the Ph.D. degree from USTC in 2002. His current research interests include parallel computing and combinatorial problem.Guo-Liang Chen was born in 1938. Now he is an Academician of CAS and Ph.D. supervisor in Department of Computer Science at USTC, director of the National High Performance Computing Center at Hefei. His current research interests include parallel computing, computer architecture and combinatorial optimization.Jun Gu was born in 1956. He received the B.S. degree in electronic engineering from USTC in 1982, and the Ph.D. degree in computer science from University of Utah. Now he is a professor and Ph.D. supervisor in computer science at USTC and Hong Kong University of Science and Technology. His main research interrests include algorithms for NP-hard problems.