Thumbnail - Request a copy

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

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005), Complexity of the min-max and min-max regret assignment problems, Operations Research Letters, 33, 6, p. 634-640. http://dx.doi.org/10.1016/j.orl.2004.12.002

Type
Article accepté pour publication ou publié
Date
2005
Journal name
Operations Research Letters
Volume
33
Number
6
Publisher
Elsevier
Pages
634-640
Publication identifier
Metadata
Show full item record
Author(s)
Aissi, Hassene
Bazgan, Cristina
Vanderpooten, Daniel
Abstract (EN)
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.
Subjects / Keywords
Complexity; NP-hard; Min–max regret; Min–max; Assignment problem