A complexity and approximability study of the bilevel knapsack problem

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

16 Citaten (Scopus)

Samenvatting

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).
Originele taal-2Engels
TitelInteger Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings)
RedacteurenM. Goemans, J. Correa
Plaats van productieBerlin
UitgeverijSpringer
Pagina's98-109
ISBN van geprinte versie978-3-642-36693-2
DOI's
StatusGepubliceerd - 2013
Evenement16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013) - Valparaíso, Chili
Duur: 18 mrt 201320 mrt 2013
Congresnummer: 16

Publicatie series

NaamLecture Notes in Computer Science
Volume7801
ISSN van geprinte versie0302-9743

Congres

Congres16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013)
Verkorte titelIPCO 2013
LandChili
StadValparaíso
Periode18/03/1320/03/13
AnderIPCO 2013

Vingerafdruk Duik in de onderzoeksthema's van 'A complexity and approximability study of the bilevel knapsack problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit