首页 | 本学科首页   官方微博 | 高级检索  
     


Backbone analysis and algorithm design for the quadratic assignment problem
Authors:He Jiang   XianChao Zhang   GuoLiang Chen  MingChu Li
Affiliation:(1) School of Software, Dalian University of Technology, Dalian, 116621, China;(2) Department of Computer Science, University of Science and Technology of China, Hefei, 230027, China
Abstract: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 beginning 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 intersection 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. Supported by the National Natural Science Foundation of China (Grant Nos 60673046 and 60673066), the Natural Science Foundation of LiaoNing Province (Grant No. 20051082), and the Gifted Young Foundation of Dalian University of Technology
Keywords:quadratic assignment problem   NP-hard   backbone analysis   biased instance   meta-heuristic
本文献已被 维普 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号