Name
Title | ||
|---|---|---|
An approximation algorithm for interval data minmax regret combinatorial optimization problems |
Abstract | ||
|---|---|---|
The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ipl.2005.11.001 | Inf. Process. Lett. |
Keywords | Field | DocType |
main result,combinatorial optimization problem,general problem,polynomial time approximation algorithm,maximal regret,polynomially solvable,interval data,approximation algorithm,performance ratio,minmax regret version,approximation algorithms,combinatorial optimization,np hard problem,information processing,polynomial time,robust optimization | Approximation algorithm,Combinatorics,Mathematical optimization,Minimax,Regret,Robust optimization,L-reduction,Combinatorial optimization,Time complexity,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
97 | 5 | 0020-0190 |
Citations | PageRank | References |
35 | 1.71 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Kasperski | 1 | 352 | 33.64 |
| Paweł Zieliński | 2 | 274 | 19.73 |