Name
Title | ||
|---|---|---|
General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.disopt.2010.03.004 | Discrete Optimization |
Keywords | DocType | Volume |
bounded number,Minimum spanning tree,Minimum weighted perfect matching,minimum weighted perfect matching,Min–max,Min–max regret,classical combinatorial optimization problem,Fptas,Knapsack,knapsack problem,Shortest path,pseudo-polynomial problem,planar graph,polynomial-time approximation scheme,Approximation,min-max regret version,general approximation scheme | Journal | 7 |
Issue | ISSN | Citations |
3 | Discrete Optimization | 13 |
PageRank | References | Authors |
0.80 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hassene Aissi | 1 | 312 | 17.03 |
| Cristina Bazgan | 2 | 679 | 62.76 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |