As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorit...As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.展开更多
基金the National Natural Science Foundation of China (Grant Nos. 60673046 and 60673066)the Natural Science Foundation of LiaoNing Province (Grant No. 20051082)the Gifted Young Foundation of Dalian University of Technology
文摘As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.
