Home > Research > Publications & Outputs > Approximation algorithms for the weight-reducib...

Links

Text available via DOI:

View graph of relations

Approximation algorithms for the weight-reducible knapsack problem

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Close
Publication date2014
Host publicationTheory and Applications of Models of Computation. TAMC 2014
Place of PublicationBerlin
PublisherSpringer
Pages203-215
Number of pages13
ISBN (Print)9783319060880
<mark>Original language</mark>English
Event11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014 - Chennai, India
Duration: 11/04/201413/04/2014

Conference

Conference11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014
Country/TerritoryIndia
CityChennai
Period11/04/1413/04/14

Publication series

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

Conference

Conference11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014
Country/TerritoryIndia
CityChennai
Period11/04/1413/04/14

Abstract

We consider the weight-reducible knapsack problem, where we are given a limited budget that can be used to decrease item weights, and we would like to optimize the knapsack objective value using such weight improvements. We develop a pseudo-polynomial algorithm for the problem, as well as a polynomial-time 3-approximation algorithm based on solving the LP-relaxation. Furthermore, we consider the special case of one degree of improvement with equal improvement costs for each item, and present a linear-time 3-approximation algorithm based on solving a cardinality-constrained and a classic knapsack problem, and show that the analysis of the polynomial-time 3-approximation algorithm can be improved to yield a 2-approximation.