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 proceedingConference contributionAcademicpeer-review

17 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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings)
EditorsM. Goemans, J. Correa
Place of PublicationBerlin
PublisherSpringer
Pages98-109
ISBN (Print)978-3-642-36693-2
DOIs
Publication statusPublished - 2013
Event16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013) - Valparaíso, Chile
Duration: 18 Mar 201320 Mar 2013
Conference number: 16

Publication series

NameLecture Notes in Computer Science
Volume7801
ISSN (Print)0302-9743

Conference

Conference16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)
Abbreviated titleIPCO 2013
Country/TerritoryChile
CityValparaíso
Period18/03/1320/03/13

Fingerprint

Dive into the research topics of 'A complexity and approximability study of the bilevel knapsack problem'. Together they form a unique fingerprint.

Cite this