Article

A robust PTAS for machine covering and packing

Authors:

Martin Skutella,

José VerschaeAuthors Info & Claims

ESA'10: Proceedings of the 18th annual European conference on Algorithms: Part I

Pages 36 - 47

Published: 06 September 2010 Publication History

Abstract

Minimizing the makespan or maximizing the minimum machine load are two of the most important and fundamental parallel machine scheduling problems. In an online scenario, jobs are consecutively added and/or deleted and the goal is to always maintain a (close to) optimal assignment of jobs to machines. The reassignment of a job induces a cost proportional to its size and the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs. Our main result is that, for any ε > 0, one can always maintain a (1 + ε)-competitive solution for some constant reassignment factor r(ε). For the minimum makespan problem this is the first improvement of the (2+ε)-competitive algorithm with constant reassignment factor published in 1996 by Andrews, Goemans, and Zhang.

References

[1]

Albers, S.: Online algorithms: a survey. Mathematical Programming 97, 3-26 (2003).

[2]

Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. Journal of Scheduling 1, 55-66 (1998).

[3]

Andrews, M., Goemans, M., Zhang, L.: Improved bounds for on-line load balancing. Algorithmica 23, 278-301 (1999).

[4]

Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Dagstuhl Seminar 1996. LNCS, vol. 1442, pp. 178-195. Springer, Heidelberg (1998).

Digital Library

[5]

Azar, Y., Epstein, L.: On-line machine covering. Journal of Scheduling 1, 67-77 (1998).

[6]

Chen, B., van Vliet, A., Woeginger, G.J.: Lower bounds for randomized online scheduling. Information Processing Letters 51, 219-222 (1994).

Digital Library

[7]

Epstein, L., Levin, A.: A robust APTAS for the classical bin packing problem. Mathematical Programming 119, 33-49 (2009).

Digital Library

[8]

Fleischer, R., Wahl, M.: Online scheduling revisited. Journal of Scheduling 3, 343- 353 (2000).

[9]

Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM 34, 144-162 (1987).

Digital Library

[10]

Rudin III, J.F., Chandrasekaran, R.: Improved bounds for the online scheduling problem. SIAM Journal on Computing 32, 717-735 (2003).

Digital Library

[11]

Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Mathematics of Operations Research 34, 481-498 (2009).

Digital Library

[12]

Sgall, J.: A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters 63, 51-55 (1997).

Digital Library

[13]

Sgall, J.: On-line scheduling -- a survey. In: Fiat, A., Woeginger, G.J. (eds.) Dagstuhl Seminar 1996. LNCS, vol. 1442, pp. 196-231. Springer, Heidelberg (1998).

Digital Library

[14]

Skutella, M., Verschae, J.: A robust PTAS for machine covering and packing. Technical Report 011-2010, Technische Universität Berlin (2010), http://www.math. tu-berlin.de/coga/publications/techreports/2010/Report-011-2010.xhtml

[15]

Westbrook, J.: Load balancing for response time. Journal of Algorithms 35, 1-16 (2000).

Digital Library

[16]

Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters 20, 149-154 (1997).

Digital Library

Cited By

Fichtenberger HLattanzi SNorouzi-Fard ASvensson OMarx D(2021)Consistent k-clustering for general metricsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458222(2660-2678)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458222
Bernstein AHolm JRotenberg ECzumaj A(2018)Online bipartite matching with amortized O(log2 n) replacementsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175331(947-959)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175331
Gupta AKrishnaswamy RKumar APanigrahi DHatami HMcKenzie PKing V(2017)Online and dynamic algorithms for set coverProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055493(537-550)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055493
Show More Cited By

Index Terms

A robust PTAS for machine covering and packing
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times
SWAT '02: Proceedings of the 8th Scandinavian Workshop on Algorithm Theory

In a scheduling problemwith controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the problemof scheduling n jobs on a single machine with controllable processing times. Each job has ...
Semi-online machine covering for two uniform machines

The machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine. We study a semi-online variant, where jobs arrive one by one, sorted by non-increasing ...
A PTAS for single machine scheduling with controllable processing times

We deal with a single machine scheduling problem in which each job has a release date, a delivery time and a controllable processing time. The fact that the jobs have a controllable processing time means that it is allowed to compress (a part of) the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ESA'10: Proceedings of the 18th annual European conference on Algorithms: Part I

September 2010

587 pages

ISBN:3642157742

Editors:
Mark de Berg
Department of Mathematics and Computing Science, TU Eindhoven, Eindhoven, The Netherlands
,
Ulrich Meyer
Institute for Computer Science, Goethe University, Frankfurt/Main, Germany

Sponsors

Springer
London Mathematical Society
University of Liverpool
EATCS: European Association for Theoretical Computer Science
International Society of Computational Geometry

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 September 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fichtenberger HLattanzi SNorouzi-Fard ASvensson OMarx D(2021)Consistent k-clustering for general metricsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458222(2660-2678)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458222
Bernstein AHolm JRotenberg ECzumaj A(2018)Online bipartite matching with amortized O(log2 n) replacementsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175331(947-959)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175331
Gupta AKrishnaswamy RKumar APanigrahi DHatami HMcKenzie PKing V(2017)Online and dynamic algorithms for set coverProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055493(537-550)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055493
Bender MFarach-Colton MFekete SFineman JGilbert SBlelloch GAgrawal K(2015)Cost-Oblivious Reallocation for Scheduling and PlanningProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755589(143-154)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755589
Gupta AKumar AStein CChekuri C(2014)Maintaining assignments onlineProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634109(468-479)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634109
Gu AGupta AKumar ABoneh DRoughgarden TFeigenbaum J(2013)The power of deferralProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488674(525-534)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488674
Epstein LLevin A(2011)Robust algorithms for preemptive schedulingProceedings of the 19th European conference on Algorithms10.5555/2040572.2040634(567-578)Online publication date: 5-Sep-2011
https://dl.acm.org/doi/10.5555/2040572.2040634
Christodoulou GKovács Avan Stee R(2010)A truthful constant approximation for maximizing the minimum load on related machinesProceedings of the 6th international conference on Internet and network economics10.5555/1940179.1940195(182-193)Online publication date: 13-Dec-2010
https://dl.acm.org/doi/10.5555/1940179.1940195

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents