Document Open Access Logo

Machine Covering in the Random-Order Model

Authors Susanne Albers, Waldo Gálvez , Maximilian Janke

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.52.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technische Universität München, Germany
Waldo Gálvez
  • Institute of Engineering Sciences, Universidad de O'Higgins, Rancagua, Chile
Maximilian Janke
  • Department of Computer Science, Technische Universität München, Germany

Funding

Work supported by the European Research Council, Grant Agreement No. 691672, project APEG.
  • Gálvez, Waldo: This project was carried out when the author was a postdoctoral researcher at the Department of Computer Science of the Technical University of Munich in Germany.

Cite As Get BibTex

Susanne Albers, Waldo Gálvez, and Maximilian Janke. Machine Covering in the Random-Order Model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.52

Abstract

In the Online Machine Covering problem jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(√m) which cannot be improved by more than a logarithmic factor.
Modern results try to mitigate this by studying semi-online models, where additional information about the job sequence is revealed in advance or extra resources are provided to the online algorithm. In this work we study the Machine Covering problem in the recently popular random-order model. Here no extra resources are present, but instead the adversary is weakened in that it can only decide upon the input set while jobs are revealed uniformly at random. It is particularly relevant to Machine Covering where lower bounds are usually associated to highly structured input sequences.
We first analyze Graham’s Greedy-strategy in this context and establish that its competitive ratio decreases slightly to Θ(m/(log(m))) which is asymptotically tight. Then, as our main result, we present an improved Õ(∜m)-competitive algorithm for the problem. This result is achieved by exploiting the extra information coming from the random order of the jobs, using sampling techniques to devise an improved mechanism to distinguish jobs that are relatively large from small ones. We complement this result with a first lower bound showing that no algorithm can have a competitive ratio of O(log(m)/{log log(m)}) in the random-order model. This lower bound is achieved by studying a novel variant of the Secretary problem, which could be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • Machine Covering
  • Online Algorithm
  • Random-Order
  • Competitive Analysis
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Susanne Albers. Better bounds for online scheduling. SIAM J. Comput., 29(2):459-473, 1999. URL: https://doi.org/10.1137/S0097539797324874.
  2. Susanne Albers and Maximilian Janke. Scheduling in the random-order model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168, pages 68:1-68:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.68.
  3. Susanne Albers and Maximilian Janke. Scheduling in the secretary model. In 41st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021. To appear. Google Scholar
  4. Susanne Albers, Arindam Khan, and Leon Ladewig. Best fit bin packing with random order revisited. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170, pages 7:1-7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.7.
  5. Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, 83(6):1750-1785, 2021. URL: https://doi.org/10.1007/s00453-021-00801-2.
  6. Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput., 39(7):2970-2989, 2010. URL: https://doi.org/10.1137/080723491.
  7. Yossi Azar and Leah Epstein. On-line machine covering. Journal of Scheduling, 1(2):67-77, 1998. URL: https://doi.org/10.1002/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y.
  8. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop (APPROX/RANDOM), volume 4627, pages 16-28. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74208-1_2.
  9. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid secretary problems. J. ACM, 65(6):35:1-35:26, 2018. URL: https://doi.org/10.1145/3212512.
  10. Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In 38th Annual ACM Symposium on Theory of Computing (STOC), pages 31-40. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132522.
  11. Yair Bartal, Amos Fiat, Howard J. Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci., 51(3):359-366, 1995. URL: https://doi.org/10.1006/jcss.1995.1074.
  12. Yair Bartal, Howard J. Karloff, and Yuval Rabani. A better lower bound for on-line scheduling. Inf. Process. Lett., 50(3):113-116, 1994. URL: https://doi.org/10.1016/0020-0190(94)00026-3.
  13. Eugene B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl, 4, 1962. Google Scholar
  14. Tomás Ebenlendr, John Noga, Jirí Sgall, and Gerhard J. Woeginger. A note on semi-online machine covering. In Approximation and Online Algorithms, Third International Workshop (WAOA), volume 3879, pages 110-118. Springer, 2005. URL: https://doi.org/10.1007/11671411_9.
  15. Leah Epstein. A survey on makespan minimization in semi-online environments. J. Sched., 21(3):269-284, 2018. URL: https://doi.org/10.1007/s10951-018-0567-z.
  16. Leah Epstein, Asaf Levin, and Rob van Stee. Max-min online allocations with a reordering buffer. SIAM J. Discret. Math., 25(3):1230-1250, 2011. URL: https://doi.org/10.1137/100794006.
  17. Ulrich Faigle, Walter Kern, and György Turán. On the performance of on-line algorithms for partition problems. Acta Cybern., 9(2):107-119, 1989. Google Scholar
  18. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. Math. Oper. Res., 43(2):638-650, 2018. URL: https://doi.org/10.1287/moor.2017.0876.
  19. Rudolf Fleischer and Michaela Wahl. Online scheduling revisited. In Algorithms, 8th Annual European Symposium (ESA), volume 1879, pages 202-210. Springer, 2000. URL: https://doi.org/10.1007/3-540-45253-2_19.
  20. Donald K. Friesen and Bryan L. Deuermeyer. Analysis of greedy solutions for a replacement part sequencing problem. Math. Oper. Res., 6(1):74-87, 1981. URL: https://doi.org/10.1287/moor.6.1.74.
  21. Gábor Galambos and Gerhard J. Woeginger. An on-line scheduling heuristic with better worst case ratio than graham’s list scheduling. SIAM J. Comput., 22(2):349-355, 1993. URL: https://doi.org/10.1137/0222026.
  22. Waldo Gálvez, José A. Soto, and José Verschae. Symmetry exploitation for online machine covering with bounded migration. ACM Trans. Algorithms, 16(4):43:1-43:22, 2020. URL: https://doi.org/10.1145/3397535.
  23. Oliver Göbel, Thomas Kesselheim, and Andreas Tönnis. Online appointment scheduling in the random order model. In Algorithms, 23rd Annual European Symposium (ESA), volume 9294, pages 680-692. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_57.
  24. Todd Gormley, Nick Reingold, Eric Torng, and Jeffery R. Westbrook. Generating adversaries for request-answer games. In 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 564-565. ACM/SIAM, 2000. Google Scholar
  25. Anupam Gupta, Ruta Mehta, and Marco Molinaro. Maximizing profit with convex costs in the random-order model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 71:1-71:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.71.
  26. Anupam Gupta and Sahil Singla. Random-order models. In Beyond the Worst-Case Analysis of Algorithms, pages 234-258. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108637435.015.
  27. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144-162, 1987. URL: https://doi.org/10.1145/7531.7535.
  28. Abdolhossein Hoorfar and Mehdi Hassani. Inequalities on the lambert w function and hyperpower function. J. Inequal. Pure and Appl. Math, 9(2):5-9, 2008. Google Scholar
  29. David R. Karger, Steven J. Phillips, and Eric Torng. A better algorithm for an ancient scheduling problem. J. Algorithms, 20(2):400-430, 1996. URL: https://doi.org/10.1006/jagm.1996.0019.
  30. Claire Kenyon. Best-fit bin-packing with random order. In 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359-364. ACM/SIAM, 1996. Google Scholar
  31. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing lps in the random-order model. SIAM J. Comput., 47(5):1939-1964, 2018. URL: https://doi.org/10.1137/15M1033708.
  32. Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630-631. SIAM, 2005. Google Scholar
  33. Oded Lachish. O(log log rank) competitive ratio for the matroid secretary problem. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 326-335. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.42.
  34. Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1859-1877. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.114.
  35. D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society, 10(1):39-51, March 1961. Google Scholar
  36. Adam Meyerson. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages 426-431. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/SFCS.2001.959917.
  37. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020. URL: https://doi.org/10.1017/9781108637435.037.
  38. Marco Molinaro. Online and random-order load balancing simultaneously. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1638-1650. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.108.
  39. Christopher J. Osborn and Eric Torng. List’s worst-average-case or WAC ratio. J. Sched., 11(3):213-215, 2008. URL: https://doi.org/10.1007/s10951-007-0019-7.
  40. John F. Rudin III. Improved bounds for the on-lijne scheduling problem. PhD thesis, The University of Texas at Dallas, 2001. Google Scholar
  41. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481-498, 2009. URL: https://doi.org/10.1287/moor.1090.0381.
  42. Martin Skutella and José Verschae. Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures. Math. Oper. Res., 41(3):991-1021, 2016. URL: https://doi.org/10.1287/moor.2015.0765.
  43. Robert J. Vanderbei. The postdoc variant of the secretary problem. Unpublished. URL: http://www.princeton.edu/~rvdb/tex/PostdocProblem/PostdocProb.pdf.
  44. Gerhard J. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett., 20(4):149-154, 1997. URL: https://doi.org/10.1016/S0167-6377(96)00055-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact