• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail - Request a copy

General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems

Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2010), General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems, Discrete Optimization, 7, 3, p. 136-148. http://dx.doi.org/10.1016/j.disopt.2010.03.004

Type
Article accepté pour publication ou publié
Date
2010
Nom de la revue
Discrete Optimization
Volume
7
Numéro
3
Éditeur
Elsevier
Pages
136-148
Identifiant publication
http://dx.doi.org/10.1016/j.disopt.2010.03.004
Métadonnées
Afficher la notice complète
Auteur(s)
Aissi, Hassene

Bazgan, Cristina

Vanderpooten, Daniel
Résumé (EN)
While the complexity of min–max and min–max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish general approximation schemes which can be used for min–max and min–max regret versions of some polynomial or pseudo-polynomial problems. Applying these schemes to shortest path, minimum spanning tree, minimum weighted perfect matching on planar graphs, and knapsack problems, we obtain fully polynomial-time approximation schemes with better running times than the ones previously presented in the literature.
Mots-clés
Knapsack; Minimum spanning tree; Min–max regret; Fptas; Min–max; Shortest path; Minimum weighted perfect matching; Approximation

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Pseudo-polynomial algorithms for min-max and min-max regret problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    Approximating min-max (regret) versions of some polynomial problems 
    Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2006) Communication / Conférence
  • Vignette de prévisualisation
    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é
  • Vignette de prévisualisation
    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
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo