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 条
  • [41] Improved approximation algorithms for some min-max postmen cover problems with applications to the min-max subtree cover
    Yu, Wei
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2023, 97 (01) : 135 - 157
  • [42] Min-max and max-min graph saturation parameters
    Sudha, S.
    Arumugam, S.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (03) : 943 - 947
  • [43] COMPLEXITY AND APPROXIMATION RESULTS FOR THE MIN-SUM AND MIN-MAX DISJOINT PATHS PROBLEMS
    Zhang, Peng
    Zhao, Wenbo
    Zhu, Daming
    COMPUTING AND INFORMATICS, 2013, 32 (01) : 23 - 45
  • [44] A SUPERLINEARLY CONVERGENT ALGORITHM FOR MIN-MAX PROBLEMS
    POLAK, E
    MAYNE, DQ
    HIGGINS, JE
    PROCEEDINGS OF THE 28TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-3, 1989, : 894 - 898
  • [45] Online learning for min-max discrete problems
    Bampis, Evripidis
    Christou, Dimitris
    Escoffier, Bruno
    NGuyen, Kim Thang
    THEORETICAL COMPUTER SCIENCE, 2022, 930 : 209 - 217
  • [46] Min-Max Problems on Factor-Graphs
    Ravanbakhsh, Siamak
    Srinivasa, Christopher
    Frey, Brendan
    Greiner, Russell
    INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 32 (CYCLE 2), 2014, 32 : 1035 - 1043
  • [47] Semidefinite programming for min-max problems and games
    Laraki, R.
    Lasserre, J. B.
    MATHEMATICAL PROGRAMMING, 2012, 131 (1-2) : 305 - 332
  • [48] Diffusion Stochastic Optimization for Min-Max Problems
    Cai, Haoyuan
    Alghunaim, Sulaiman A.
    Sayed, Ali H.
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2025, 73 : 259 - 274
  • [49] SUPERLINEARLY CONVERGENT ALGORITHM FOR MIN-MAX PROBLEMS
    POLAK, E
    MAYNE, DQ
    HIGGINS, JE
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1991, 69 (03) : 407 - 439
  • [50] Approximation algorithms for min-max and max-min resource sharing problems, and applications
    Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel, Olshausenstr. 40, 24098 Kiel, Germany
    Lect. Notes Comput. Sci., 2006, (156-202):
12345