• 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

Approximation of min-max and min-max regret versions of some combinatorial optimization problems

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007), Approximation of min-max and min-max regret versions of some combinatorial optimization problems, European Journal of Operational Research, 179, 2, p. 281-290. http://dx.doi.org/10.1016/j.ejor.2006.03.023

Type
Article accepté pour publication ou publié
Date
2007
Journal name
European Journal of Operational Research
Volume
179
Number
2
Pages
281-290
Publication identifier
http://dx.doi.org/10.1016/j.ejor.2006.03.023
Metadata
Show full item record
Author(s)
Aissi, Hassene

Bazgan, Cristina

Vanderpooten, Daniel
Abstract (EN)
This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.
Subjects / Keywords
Knapsack; Min–max regret; Shortest path; Minimum spanning tree; Approximation

Related items

Showing items related by title and author.

  • 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
    General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié
  • Thumbnail
    Approximating min-max (regret) versions of some polynomial problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2006) Communication / Conférence
  • 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
  • Thumbnail
    Approximation and resolution of min–max and min–max regret versions of combinatorial optimization problems 
    Aissi, Hassene (2006) Article accepté pour publication ou publié
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