Improved approximation algorithms for a bilevel knapsack problem

X. Qui, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)


We study the Stackelberg/bilevel knapsack problem as proposed by Chen and Zhang [4]: Consider two agents, a leader and a follower. Each has his own knapsack. (Knapsack capacities are possibly different). As usual, there is a set of items $i = 1, ..., n$ of given weight $w_i$ and profits $p_i$. It is allowed to pack item $i$ into both knapsacks, but in this case the corresponding profit for each player becomes $p_i + a_i$, where $a_i$ is a given (positive or negative) number. The objective is to find a packing for the leader such that the total profit of the two knapsacks is maximized, assuming that the follower acts selfishly. We present tight approximation algorithms for all settings considered in [4].
Original languageEnglish
Title of host publication20th International Conference on Computing and Combinatorics , COCOON 2014
EditorsZhipeng Cai, Alex Zelikovsky, Anu Bourgeois
Place of PublicationLondon
Number of pages12
ISBN (Print)978-3-319-08782-5
Publication statusPublished - 4 Aug 2014
Event20th International Conference on Computing and Combinatorics: COCOON 2014 - Atlanta, United States
Duration: 4 Aug 20146 Aug 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Computing and Combinatorics
Country/TerritoryUnited States


  • EWI-25175
  • METIS-309609
  • IR-93162


Dive into the research topics of 'Improved approximation algorithms for a bilevel knapsack problem'. Together they form a unique fingerprint.

Cite this