Backbone analysis and algorithm design for the quadratic assignment problem
Backbone analysis and algorithm design for the quadratic assignment problem
复制标题
二次分配问题的主干分析和算法设计
DOI：
10.1007/s11432-008-0042-0
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Li MingChu
中科院分区：
文献类型：
--
作者：
Chen GuoLiang;Jiang He;Zhang XianChao;Li MingChu
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.
登录
查看更多内容
DOI：
10.1145/321958.321975
发表时间：
1976-07
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
S. Sahni;T. Gonzalez
通讯作者：
S. Sahni;T. Gonzalez
影响因子：
3.6
作者：
L. Gambardella;É. Taillard;M. Dorigo
通讯作者：
L. Gambardella;É. Taillard;M. Dorigo
DOI：
--
发表时间：
2005-07
期刊：
--
影响因子：
--
作者：
P. Kilby;J. Slaney;T. Walsh
通讯作者：
P. Kilby;J. Slaney;T. Walsh
影响因子：
6.4
作者：
R. Burkard;S. E. Karisch;F. Rendl
通讯作者：
R. Burkard;S. E. Karisch;F. Rendl
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
Carlos A. S. Oliveira;P. Pardalos;M. G. Resende
通讯作者：
Carlos A. S. Oliveira;P. Pardalos;M. G. Resende