Name
Abstract | ||
|---|---|---|
We analyze three fundamental variants of the bilevel knapsack problem, which all are complete for the second level of the polynomial hierarchy. If the weight and profit coefficients in the knapsack problem are encoded in unary, then two of the bilevel variants are solvable in polynomial time, whereas the third is NP-complete. Furthermore we design a polynomial time approximation scheme for this third variant, whereas the other two variants cannot be approximated in polynomial time within any constant factor (assuming P≠NP). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-36694-9_9 | IPCO |
Keywords | Field | DocType |
constant factor,profit coefficient,bilevel knapsack problem,polynomial time approximation scheme,knapsack problem,polynomial hierarchy,bilevel variant,polynomial time,approximability study,fundamental variant | Polynomial hierarchy,Discrete mathematics,Mathematical optimization,Combinatorics,Pseudo-polynomial time,Unary operation,Continuous knapsack problem,Vertex cover,Knapsack problem,Time complexity,Polynomial-time approximation scheme,Mathematics | Conference |
Citations | PageRank | References |
9 | 0.63 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Caprara | 1 | 1729 | 160.76 |
| Margarida Carvalho | 2 | 29 | 5.34 |
| Andrea Lodi | 3 | 2198 | 152.51 |
| Gerhard Woeginger | 4 | 4176 | 384.37 |