Approximation algorithms for a bi-level knapsack problem

Lin Chen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
Pages399-410
Number of pages12
DOIs
StatePublished - 2011
Event5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 - Zhangjiajie, China
Duration: Aug 4 2011Aug 6 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6831 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
CountryChina
CityZhangjiajie
Period08/4/1108/6/11

Keywords

  • Approximation algorithms
  • Bilevel knapsack problem

Fingerprint Dive into the research topics of 'Approximation algorithms for a bi-level knapsack problem'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., & Zhang, G. (2011). Approximation algorithms for a bi-level knapsack problem. In Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings (pp. 399-410). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6831 LNCS). https://doi.org/10.1007/978-3-642-22616-8_31