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

被引：65

作者：

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 [J].