• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2008
Journal name
Discrete Optimization
Volume
5
Number
1
Publisher
Elsevier
Pages
66-73
Publication identifier
http://dx.doi.org/10.1016/j.disopt.2007.11.008
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 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–max

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity of the min-max (regret) versions of cut problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
  • Thumbnail
    Complexity of the min-max and min-max regret assignment problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of min-max and min-max regret versions of some combinatorial optimization problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
  • Thumbnail
    Min–max and min–max regret versions of combinatorial optimization problems: A survey 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009) Article accepté pour publication ou publié
  • Thumbnail
    Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo