• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

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

Thumbnail
Date
2007
Indexation documentaire
Principes généraux des mathématiques
Subject
Knapsack; Min–max regret; Shortest path; Minimum spanning tree; Approximation
Nom de la revue
European Journal of Operational Research
Volume
179
Numéro
2
Date de publication
2007
Pages article
281-290
DOI
http://dx.doi.org/10.1016/j.ejor.2006.03.023
URI
https://basepub.dauphine.fr/handle/123456789/2220
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Aissi, Hassene
Bazgan, Cristina
Vanderpooten, Daniel
Type
Article accepté pour publication ou publié
Résumé en anglais
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.