Improved approximation algorithms for a bilevel knapsack problem

X. Qui, Walter Kern

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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].
Original languageEnglish
Title of host publication20th International Conference on Computing and Combinatorics , COCOON 2014
EditorsZhipeng Cai, Alex Zelikovsky, Anu Bourgeois
Place of PublicationLondon
PublisherSpringer
Pages312-323
Number of pages12
ISBN (Print)978-3-319-08782-5
DOIs
Publication statusPublished - 4 Aug 2014
Event20th International Conference on Computing and Combinatorics: COCOON 2014 - Atlanta, United States
Duration: 4 Aug 20146 Aug 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8591
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Computing and Combinatorics
CountryUnited States
CityAtlanta
Period4/08/146/08/14

Keywords

  • EWI-25175
  • METIS-309609
  • IR-93162

Fingerprint

Dive into the research topics of 'Improved approximation algorithms for a bilevel knapsack problem'. Together they form a unique fingerprint.

Cite this