TY - GEN
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 - 2011
Y1 - 2011
N2 - In this paper, we consider a variant of 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 can 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 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 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 can 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 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=80051996924&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-22616-8_31
DO - 10.1007/978-3-642-22616-8_31
M3 - Conference contribution
AN - SCOPUS:80051996924
SN - 9783642226151
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 399
EP - 410
BT - Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
T2 - 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
Y2 - 4 August 2011 through 6 August 2011
ER -