Title | ||
---|---|---|
On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data |
Abstract | ||
---|---|---|
The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.orl.2006.09.007 | Oper. Res. Lett. |
Keywords | Field | DocType |
combinatorial optimization problem,minmax regret,minmax regret combinatorial optimization,pseudopolynomial algorithm,polynomial time approximation scheme,interval cost,maximal regret,general problem,fptas,interval data,combinatorial optimization,fully polynomial time approximation scheme | Combinatorics,Mathematical optimization,Minimax,Regret,Combinatorial optimization problem,Combinatorial optimization,Time complexity,Optimization problem,Polynomial-time approximation scheme,Mathematics,Interval data | Journal |
Volume | Issue | ISSN |
35 | 4 | Operations Research Letters |
Citations | PageRank | References |
11 | 0.65 | 10 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Adam Kasperski | 1 | 352 | 33.64 |
Paweł Zieliński | 2 | 274 | 19.73 |