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
2010Nom de la revue
Discrete OptimizationVolume
7Numéro
3Éditeur
Elsevier
Pages
136-148
Identifiant publication
Métadonnées
Afficher la notice complèteRé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; ApproximationPublications associées
Affichage des éléments liés par titre et auteur.
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2006) Communication / Conférence
-
Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2009) Article accepté pour publication ou publié
-
Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack Aissi, Hassene; Bazgan, Cristina; Vanderpooten, Daniel (2005) Communication / Conférence