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
相关论文
共 50 条
  • [21] Algorithms for the Min-max Regret Generalized Assignment Problem with Interval Data
    Wu, W.
    Iori, M.
    Martello, S.
    Yagiura, M.
    2014 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2014, : 734 - 738
  • [22] Min-Max quickest path problems
    Ruzika, Stefan
    Thiemann, Markus
    NETWORKS, 2012, 60 (04) : 253 - 258
  • [23] ON A MIN-MAX THEOREM
    CHEN FANGQI
    AppliedMathematics:AJournalofChineseUniversities(SeriesB), 1997, (03) : 43 - 48
  • [24] Parallel Approximation of Min-Max Problems
    Gus Gutoski
    Xiaodi Wu
    computational complexity, 2013, 22 : 385 - 428
  • [25] Min-max controllable risk problems
    Gurevsky, Evgeny
    Kovalev, Sergey
    Kovalyov, Mikhail Y.
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2021, 19 (01): : 93 - 101
  • [26] Min-max controllable risk problems
    Evgeny Gurevsky
    Sergey Kovalev
    Mikhail Y. Kovalyov
    4OR, 2021, 19 : 93 - 101
  • [27] ON MIN-MAX INTEGER ALLOCATION PROBLEMS
    ICHIMORI, T
    OPERATIONS RESEARCH, 1984, 32 (02) : 449 - 450
  • [28] Parallel Approximation of Min-Max Problems
    Gutoski, Gus
    Wu, Xiaodi
    COMPUTATIONAL COMPLEXITY, 2013, 22 (02) : 385 - 428
  • [29] Min-Max Propagation
    Srinivasa, Christopher
    Givoni, Inmar
    Ravanbakhsh, Siamak
    Frey, Brendan J.
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 30 (NIPS 2017), 2017, 30
  • [30] On the complexity and approximation of the min-sum and min-max disjoint paths problems
    Zhang, Peng
    Zhao, Wenbo
    COMBINATORICS, ALGORITHMS, PROBABILISTIC AND EXPERIMENTAL METHODOLOGIES, 2007, 4614 : 70 - +
12345