Complexity of the min-max (regret) versions of cut problems
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2008), Complexity of the min-max (regret) versions of cut problems, Discrete Optimization, 5, 1, p. 66-73. http://dx.doi.org/10.1016/j.disopt.2007.11.008
Type
Article accepté pour publication ou publiéDate
2008Journal name
Discrete OptimizationVolume
5Number
1Publisher
Elsevier
Pages
66-73
Publication identifier
Metadata
Show full item recordAbstract (EN)
This paper investigates the complexity of the min–max and min–max regret versions of the min s–t cut and min cut problems. Even if the underlying problems are closely related and both polynomial, the complexities of their min–max and min–max regret versions, for a constant number of scenarios, are quite contrasted since they are respectively strongly NP-hard and polynomial. However, for a non-constant number of scenarios, these versions become strongly NP-hard for both problems. In the interval scenario case, min–max versions are trivially polynomial. Moreover, for min–max regret versions, we obtain the same contrasted results as for a constant number of scenarios: min–max regret min s–t cut is strongly NP-hard whereas min–max regret min cut is polynomial.Subjects / Keywords
Complexity; Min–max regret; Min s–t cut; Min cut; Min–maxRelated items
Showing items related by title and author.
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) 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