Name
Abstract | ||
|---|---|---|
Min–max and min–max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min–max and min–max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s–t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ejor.2008.09.012 | European Journal of Operational Research |
Keywords | Field | DocType |
Min–max,Min–max regret,Combinatorial optimization,Complexity,Approximation,Robustness | Combinatorics,Mathematical optimization,Regret,Combinatorial optimization problem,Shortest path problem,L-reduction,Combinatorial optimization,Robustness (computer science),Spanning tree,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
197 | 2 | 0377-2217 |
Citations | PageRank | References |
148 | 4.96 | 47 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hassene Aissi | 1 | 312 | 17.03 |
| Cristina Bazgan | 2 | 679 | 62.76 |
| Daniel Vanderpooten | 3 | 1153 | 74.66 |