@inproceedings{50c0a7e95e0748759b0569554715d400,

title = "Improved approximation algorithms for a bilevel knapsack problem",

abstract = "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].",

keywords = "EWI-25175, METIS-309609, IR-93162",

author = "X. Qui and Walter Kern",

year = "2014",

month = aug,

day = "4",

doi = "10.1007/978-3-319-08783-2_27",

language = "English",

isbn = "978-3-319-08782-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "312--323",

editor = "Zhipeng Cai and Alex Zelikovsky and Anu Bourgeois",

booktitle = "20th International Conference on Computing and Combinatorics , COCOON 2014",

address = "Germany",

note = "20th International Conference on Computing and Combinatorics : COCOON 2014 ; Conference date: 04-08-2014 Through 06-08-2014",

}