• 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

Pseudo-polynomial algorithms for min-max and min-max regret problems

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005), Pseudo-polynomial algorithms for min-max and min-max regret problems, in Xian-Sun, Zhang, Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings, World Publishing Corporation, p. 171-178

View/Open
pseudo_polynomial.PDF (126.7Kb)
Type
Communication / Conférence
Date
2005
Conference country
CHINA
Book title
Operations Research and Its Applications. The Fifth International Symposium, ISORA’05 Tibet, China, August 8–13, 2005 Proceedings
Book author
Xian-Sun, Zhang
Publisher
World Publishing Corporation
ISBN
7-5062-7277-6
Pages
171-178
Metadata
Show full item record
Author(s)
Aissi, Hassene

Bazgan, Cristina

Vanderpooten, Daniel
Abstract (EN)
We present in this paper general pseudo-polynomial time algorithms to solve min-maxand min-max regret versions of some polynomial or pseudo-polynomial problems undera constant number of scenarios. Using easily computable bounds, we can improve thesealgorithms. This way we provide pseudo-polynomial algorithms for the min-max and andmin-max regret versions of several classical problems including minimum spanning tree,shortest path, and knapsack.
Subjects / Keywords
min-max; pseudo-polynomial; computational complexity; min-max regret

Related items

Showing items related by title and author.

  • 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
    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
    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 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
    Approximating min-max (regret) versions of some polynomial problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2006) 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