Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brotcorne, L., Hanafi, S., Mansi, R.: A dynamic programming algorithm for the bi-level knapsack problem. Operations Research Letters 37, 215–218 (2009)
Colson, B., Marcotte, P., Savard, G.: Bilevel programming, A survey. 4OR: A Quarterly Journal of Operations Research 3(2), 87–107 (2005)
Dempe, S., Richter, K.: Bilevel programming with Knapsack constraint. Central European Journal of Operations Research 8, 93–107 (2000)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22, 363–468 (1975)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp. 404–413 (1999)
Loridan, P., Morgan, J.: Weak via strong Stackelberg problem: Newresults. Journal of Global Optimization 8, 263–287 (1996)
Wang, Z., Xing, W., Fang, S.C.: Two-group knapsack game. Theoretical Computer Science 411, 1094–1103 (2010)
Wang, Z., Xing, W.: Two-person knapsack game. Journal of Industrial and Management Optimization 6(4), 847–860 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, L., Zhang, G. (2011). Approximation Algorithms for a Bi-level Knapsack Problem. In: Wang, W., Zhu, X., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2011. Lecture Notes in Computer Science, vol 6831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22616-8_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-22616-8_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22615-1
Online ISBN: 978-3-642-22616-8
eBook Packages: Computer ScienceComputer Science (R0)