¡¡Chinese Journal of Computers   Full Text
  TitleBackbone Analysis and Heuristic Design for the Graph Partitioning Problem
  AuthorsJIANG He1),2) QIU Tie1)
  Address1)(School of Software, Dalian University of Technology, Dalian, Liaoning 116621)
2)(State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190)
  Year2009
  IssueNo.8(1662¡ª1667)
  Abstract &
  Background 		Abstract The graph partitioning problem (GPP) is one of the typical NP-Hard problems with extensively wide applications. Efficient heuristics have been the hotline in this research area at all times. There exist defects of theoretic results and limited size in backbone analysis, a useful tool for heuristic design of the GPP. In this paper, by constructing the biased instance, it is proved that it is NP-Hard to obtain the GPP backbone, and the backbone size is increased through analyzing the relationship between the biased GPP instance and general GPP instances. Furthermore, the biased instance-IBS (BI-IBS) is proposed to improve the IBS which is one of the best heuristics for the GPP. In this new heuristic, after a biased GPP instance was built and reduced by intersection of local optimal solutions, the reduced instance was then solved. Experiments indicate that the BI-IBS had achieved better performance than existing heuristics in terms of solution quality. Not only this work solved existing problems in research of the GPP backbone, but the skill of biased instance construction threw a light on the theoretic analysis of backbone and heuristic design for other NP-Hard problems.
Keywords graph partitioning problem; NP-hard; backbone analysis; heuristic design
Background This project is supported by the National Natural Science Foundation of China (60805024), the National Research Foundation for the Doctoral Program of Higher Education of China (20070141020). It focuses on the efficient heuristics for classic NP-Hard problems (such as SAT, TSP, Bin-Packing and GPP).
The group has presented some fast heuristics and theoretic results of NP-Hard problems and published many papers on Journal of Combinatorial Optimization,Discrete Mathematics,Information Processing Letters,Journal of Computer Science and Technology,Journal of Advanced Software,Chinese Journal of Computers(in Chinese),Journal of Software(in Chinese),etc.And being a part of this project,this paper mainly focuses on the heuristic design of the graph partitioning problem.