On the advice complexity of the knapsack problem
METADATA ONLY
Loading...
Author / Producer
Date
2011-09
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study the advice complexity and the random bit complexity of the online knapsack problem: Given a knapsack of unit capacity, and n items that arrive in successive time steps, an online algorithm has to decide for every item whether it gets packed into the knapsack or not. The goal is to put as much valuable items as possible into it without exceeding its capacity. In the model of advice complexity of online problems, one asks how many bits of advice about the unknown parts of the input are both necessary and sufficient to achieve a specific competitive ratio. It is well-known that even the unweighted online knapsack problem does not admit any competitive deterministic online algorithm. We show that a single bit of advice helps a deterministic algorithm to become 2-competitive, but that Omega(log(n)) advice bits are necessary to further improve the deterministic competitive ratio. This is the first time that such a phase transition for the number of advice bits has been observed for any problem. We also show that, surprisingly, instead of an advice bit, a single random bit allows for a competitive ratio of 2, and any further amount of randomness does not improve this. Moreover, we prove that, in a resource augmentation model, i.e., when allowing a little overpacking of the knapsack, a constant number of advice bits suffices to achieve a near-optimal competitive ratio. We also study the weighted version of the problem proving that, with O(log(n)) bits of advice, we can get arbitrarily close to an optimal solution and, using asymptotically fewer bits, we are not competitive.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
740
Pages / Article No.
Publisher
ETH Zurich, Department of Computer Science, Information Technology and Education
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Online algorithms; Advice complexity; Competitive ratio; Knapsack problem
Organisational unit
03666 - Hromkovic, Juraj (emeritus) / Hromkovic, Juraj (emeritus)