A complexity and approximability study of the bilevel knapsack problem

A. Caprara; M. Carvalho; A. Lodi; G.J. Woeginger

doi:10.1007/978-3-642-36694-9_9

A complexity and approximability study of the bilevel knapsack problem

A. Caprara, M. Carvalho, A. Lodi, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

20 Citations (Scopus)

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).

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings)
Editors	M. Goemans, J. Correa
Place of Publication	Berlin
Publisher	Springer
Pages	98-109
ISBN (Print)	978-3-642-36693-2
DOIs	https://doi.org/10.1007/978-3-642-36694-9_9
Publication status	Published - 2013
Event	16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013) - Valparaíso, Chile Duration: 18 Mar 2013 → 20 Mar 2013 Conference number: 16

Publication series

Name	Lecture Notes in Computer Science
Volume	7801
ISSN (Print)	0302-9743

Conference

Conference	16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)
Abbreviated title	IPCO 2013
Country/Territory	Chile
City	Valparaíso
Period	18/03/13 → 20/03/13

Access to Document

10.1007/978-3-642-36694-9_9

Cite this

Caprara, A., Carvalho, M., Lodi, A., & Woeginger, G. J. (2013). A complexity and approximability study of the bilevel knapsack problem. In M. Goemans, & J. Correa (Eds.), Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings) (pp. 98-109). (Lecture Notes in Computer Science; Vol. 7801). Springer. https://doi.org/10.1007/978-3-642-36694-9_9

Caprara, A. ; Carvalho, M. ; Lodi, A. et al. / A complexity and approximability study of the bilevel knapsack problem. Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings). editor / M. Goemans ; J. Correa. Berlin : Springer, 2013. pp. 98-109 (Lecture Notes in Computer Science).

@inproceedings{d605472b4a6d4261bc18492ba08799cd,

title = "A complexity and approximability study of the bilevel knapsack problem",

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).",

author = "A. Caprara and M. Carvalho and A. Lodi and G.J. Woeginger",

year = "2013",

doi = "10.1007/978-3-642-36694-9\_9",

language = "English",

isbn = "978-3-642-36693-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "98--109",

editor = "M. Goemans and J. Correa",

booktitle = "Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valpara{\'i}so, Chile, March 18-20, 2013. Proceedings)",

address = "Germany",

note = "16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013), IPCO 2013 ; Conference date: 18-03-2013 Through 20-03-2013",

}

Caprara, A, Carvalho, M, Lodi, A & Woeginger, GJ 2013, A complexity and approximability study of the bilevel knapsack problem. in M Goemans & J Correa (eds), Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings). Lecture Notes in Computer Science, vol. 7801, Springer, Berlin, pp. 98-109, 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013), Valparaíso, Chile, 18/03/13. https://doi.org/10.1007/978-3-642-36694-9_9

A complexity and approximability study of the bilevel knapsack problem. / Caprara, A.; Carvalho, M.; Lodi, A. et al.
Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings). ed. / M. Goemans; J. Correa. Berlin: Springer, 2013. p. 98-109 (Lecture Notes in Computer Science; Vol. 7801).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A complexity and approximability study of the bilevel knapsack problem

AU - Caprara, A.

AU - Carvalho, M.

AU - Lodi, A.

AU - Woeginger, G.J.

N1 - Conference code: 16

PY - 2013

Y1 - 2013

N2 - 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).

AB - 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).

U2 - 10.1007/978-3-642-36694-9_9

DO - 10.1007/978-3-642-36694-9_9

M3 - Conference contribution

SN - 978-3-642-36693-2

T3 - Lecture Notes in Computer Science

SP - 98

EP - 109

BT - Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings)

A2 - Goemans, M.

A2 - Correa, J.

PB - Springer

CY - Berlin

T2 - 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)

Y2 - 18 March 2013 through 20 March 2013

ER -

Caprara A, Carvalho M, Lodi A, Woeginger GJ. A complexity and approximability study of the bilevel knapsack problem. In Goemans M, Correa J, editors, Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings). Berlin: Springer. 2013. p. 98-109. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-36694-9_9

A complexity and approximability study of the bilevel knapsack problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this