TY - JOUR
T1 - Approximation algorithms for a bi-level knapsack problem
AU - Chen, Lin
AU - Zhang, Guochuan
N1 - Funding Information:
Corresponding author. E-mail addresses: chenlin198662@zju.edu.cn (L. Chen), zgc@zju.edu.cn (G. Zhang). 1 Research is supported by NSFC (10971192).
PY - 2013/7/29
Y1 - 2013/7/29
N2 - In this paper, we consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. The two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously to different knapsacks. However, in this case the profit of such items may vary. One agent packs items into his knapsack to maximize the total profit, while another agent can only pack items into his knapsack as well but he cares about the total profits of items packed into two knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results.
AB - In this paper, we consider a variant of the knapsack problem. There are two knapsacks with probably different capacities, owned by two agents respectively. Given a set of items, each with a fixed size and a profit. The two agents select items and pack them into their own knapsacks under the capacity constraint. Same items can be packed simultaneously to different knapsacks. However, in this case the profit of such items may vary. One agent packs items into his knapsack to maximize the total profit, while another agent can only pack items into his knapsack as well but he cares about the total profits of items packed into two knapsacks. The latter agent is a leader while the former is a follower. We aim at designing an approximation algorithm for the leader assuming that the follower is selfish. For different settings we provide approximation results.
KW - Approximation algorithms
KW - Bilevel knapsack problem
UR - http://www.scopus.com/inward/record.url?scp=84881166598&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.08.008
DO - 10.1016/j.tcs.2012.08.008
M3 - Article
AN - SCOPUS:84881166598
SN - 0304-3975
VL - 497
SP - 1
EP - 12
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -