Complexity of the min-max and min-max regret assignment problems

被引：63

作者：

Aissi, H ^{[1
]}

Bazgan, C ^{[1
]}

Vanderpooten, D ^{[1
]}

机构：

[1] Univ Paris 09, LAMSADE, F-75775 Paris, France

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 06期

关键词：

assignment problem; min-max; min-max regret; complexity; NP-hard;

D O I：

10.1016/j.orl.2004.12.002

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：634 / 640

页数：7

共 11 条

[1] [Anonymous], 2001, ROBUST SHORTEST PATH
[2] On the complexity of the robust spanning tree problem with interval data
Aron, ID
Van Hentenryck, P
[J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (01) : 36 - 40
[3] Interval data minmax regret network optimization problems
Averbakh, I
Lebedev, V
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) : 289 - 301
[4] Minmax regret linear resource allocation problems
Averbakh, I
[J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (02) : 174 - 180
[5] Complexity of robust single facility location problems on networks with uncertain edge lengths
Averbakh, I
[J]. DISCRETE APPLIED MATHEMATICS, 2003, 127 (03) : 505 - 522
[6] Carey M., 1979, COMPUTER INTRACTABIL
[7] HOFFMAN AJ, 1963, NAV RES LOG, V10, P375, DOI DOI 10.1002/NAV.3800100132
[8] Kouvelis P., 1997, ROBUST DISCRETE OPTI
[9] Kuhn H.W., 1955, HUNGARIAN METHOD ASS, V2, P83, DOI [DOI 10.1002/NAV.20053, DOI 10.1002/NAV.3800020109]
[10] The robust spanning tree problem with interval data
Yaman, H
Karasan, OE
Pinar, MÇ
[J]. OPERATIONS RESEARCH LETTERS, 2001, 29 (01) : 31 - 40

← 1 2 →