Two classes of Quadratic Assignment Problems that are solvable as Linear Assignment Problems

被引：10

作者：

Erdogan, Gunes ^{[1
]}

Tansel, Barbaros C. ^{[2
]}

机构：

[1] Ozyegin Univ, Dept Ind Engn, TR-34662 Istanbul, Turkey

[2] Bilkent Univ, Dept Ind Engn, TR-06800 Ankara, Turkey

来源：

DISCRETE OPTIMIZATION | 2011年 / 8卷 / 03期

关键词：

Quadratic Assignment Problem; Linear Assignment Problem; Computational complexity; Polynomial time solvability;

D O I：

10.1016/j.disopt.2011.03.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Quadratic Assignment Problem is one of the hardest combinatorial optimization problems known. We present two new classes of instances of the Quadratic Assignment Problem that can be reduced to the Linear Assignment Problem and give polynomial time procedures to check whether or not an instance is an element of these classes. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：446 / 451

页数：6

共 13 条

[1] [Anonymous], 1998, The Quadratic Assignment Problem Theory and Algorithm
[2] [Anonymous], 1992, Combinatorial optimization
[3] BRIXIUS NW, 2001, STEINBERG WIRING PRO
[4] Burkard R., 2009, ASSIGNMENT PROBLEMS
[5] Burkard R.E., 1995, 34 SFB TU GRAZ I MAT
[6] QAPLIB - A quadratic assignment problem library
Burkard, RE
Karisch, SE
Rendl, F
[J]. JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (04) : 391 - 403
[7] BURKARD RE, 1997, 104 SFB TU GRAZ I MA
[8] SPECIAL CASES OF THE QUADRATIC ASSIGNMENT PROBLEM
CHEN, BT
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 81 (02) : 410 - 419
[9] A solvable case of the quadratic assignment problem
Deineko, VG
Woeginger, GJ
[J]. OPERATIONS RESEARCH LETTERS, 1998, 22 (01) : 13 - 17
[10] ASSIGNMENT PROBLEMS AND THE LOCATION OF ECONOMIC-ACTIVITIES
KOOPMANS, TC
BECKMANN, M
[J]. ECONOMETRICA, 1957, 25 (01) : 53 - 76

← 1 2 →