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
2005Journal name
Operations Research LettersVolume
33Number
6Publisher
Elsevier
Pages
634-640
Publication identifier
Metadata
Show full item recordAbstract (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 problemRelated items
Showing items related by title and author.
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2008) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009) Article accepté pour publication ou publié
-
Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence