Please use this identifier to cite or link to this item:
Title: Online algorithms with advice for bin packing and scheduling problems
Authors: Renault, Marc P.
Rosén, Adi
van Stee, Rob
First Published: 31-Jul-2015
Publisher: Elsevier
Citation: Theoretical Computer Science, 2015, 600, pp. 155-170
Abstract: We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is (1+ε)-competitive and uses O(1εlog 1ε) bits of advice per request. For scheduling on m identical machines, with the objective function of any of makespan, machine covering and the minimization of the ℓ<inf>p</inf> norm, p>1, we give similar results. We give online algorithms with advice which are (1+ε)-competitive ((1/(1-ε))-competitive for machine covering) and also use O(1εlog 1ε) bits of advice per request. We complement our results by giving a lower bound that shows that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least (1-2mn)log m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed.
DOI Link: 10.1016/j.tcs.2015.07.050
ISSN: 0304-3975
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © Elsevier, 2015. This is an open-access article distributed under the terms of the Creative Commons Attribution-Non Commercial-No Derivatives License ( ), which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
adviceptas-TCS-Rev2.pdfPost-review (final submitted)383.23 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.