LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times

Alexander Grigoriev, Maxim Sviridenko, Marc Uetz

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

7 Citations (Scopus)

Abstract

We consider a scheduling problem on unrelated parallel machines with the objective to minimize the makespan. In addition to its machine dependence, the processing time of any job is dependent on the usage of a scarce renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time. The more of the resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied by Shmoys and Tardos. On the basis of an integer linear programming formulation for (a relaxation of) the problem, we adopt a randomized LP rounding technique from Kumar et al. (FOCS 2005) in order to obtain a deterministic, integral LP solution that is close to optimum. We show how this rounding procedure can be used to derive a deterministic 3.75-approximation algorithm for the scheduling problem. This improves upon previous results, namely a deterministic 6.83-approximation, and a randomized 4-approximation. The improvement is due to the better LP rounding and a new scheduling algorithm that can be viewed as a restricted version of the harmonic algorithm for bin packing.
Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Subtitle of host publication9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006. Proceedings
EditorsJosep Díaz, Klaus Jansen, José D.P. Rolim, Uri Zwick
PublisherSpringer
Pages140-151
Number of pages12
ISBN (Electronic)978-3-540-38045-0
ISBN (Print)978-3-540-38044-3
DOIs
Publication statusPublished - 2006
Event9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 - Barcelona, Spain
Duration: 28 Aug 200630 Aug 2006
Conference number: 9

Publication series

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

Conference

Conference9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006
Abbreviated titleAPPROX
CountrySpain
CityBarcelona
Period28/08/0630/08/06

Fingerprint

Dive into the research topics of 'LP rounding and an almost harmonic algorithm for scheduling with resource dependent processing times'. Together they form a unique fingerprint.

Cite this