Complexity of the min-max (regret) versions of cut problems
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005), Complexity of the min-max (regret) versions of cut problems, in Du, Ding-Zhu, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Springer : Berlin Heidelberg, p. 789-798
TypeCommunication / Conférence
Book titleAlgorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
Book authorDu, Ding-Zhu
MetadataShow full item record
Abstract (EN)This paper investigates the complexity of the min-max and min-max regret versions of the s–t min cut and min cut problems. Even if the underlying problems are closely related and both polynomial, we show that the complexity 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. Thus, we exhibit the first polynomial problem, s–t min cut, whose min-max (regret) versions are strongly NP-hard. Also, min cut is one of the few polynomial problems whose min-max (regret) versions remain polynomial. However, these versions become strongly NP-hard for a non constant number of scenarios. In the interval data case, min-max versions are trivially polynomial. Moreover, for min-max regret versions, we obtain the same contrasted result as for a constant number of scenarios: min-max regret s–t cut is strongly NP-hard whereas min-max regret cut is polynomial.
Subjects / Keywordsmin-max regret; s–t min cut; min cut; min-max; complexity
Showing items related by title and author.
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié