Document Open Access Logo

Scheduling in the Secretary Model

Authors Susanne Albers, Maximilian Janke

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.6.pdf
  • Filesize: 0.88 MB
  • 22 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technische Universität München, Germany
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.

Cite As Get BibTex

Susanne Albers and Maximilian Janke. Scheduling in the Secretary Model. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.FSTTCS.2021.6

Abstract

This paper studies online makespan minimization in the secretary model. Jobs, specified by their processing times, are presented in a uniformly random order. The input size n is known in advance. An online algorithm has to non-preemptively assign each job permanently and irrevocably to one of m parallel and identical machines such that the expected time it takes to process them all, the makespan, is minimized.
We give two deterministic algorithms. First, a straightforward adaptation of the semi-online strategy Light Load [Albers and Hellwig, 2012] provides a very simple approach retaining its competitive ratio of 1.75. A new and sophisticated algorithm is 1.535-competitive. These competitive ratios are not only obtained in expectation but, in fact, for all but a very tiny fraction of job orders.
Classically, online makespan minimization only considers the worst-case order. Here, no competitive ratio below 1.885 for deterministic algorithms and 1.581 using randomization is possible. The best randomized algorithm so far is 1.916-competitive. Our results show that classical worst-case orders are quite rare and pessimistic for many applications.
We complement our results by providing first lower bounds. A competitive ratio obtained on nearly all possible job orders must be at least 1.257. This implies a lower bound of 1.043 for both deterministic and randomized algorithms in the general model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Scheduling
  • makespan minimization
  • online algorithm
  • competitive analysis
  • lower bound
  • random-order
  • secretary problem

Metrics

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

Related Versions

References

  1. S. Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2):459-473, 1999. Publisher: SIAM. Google Scholar
  2. S. Albers. On randomized online scheduling. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 134-143, 2002. Google Scholar
  3. S. Albers, W. Gálvez, and M. Janke. Machine covering in the random-order model. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  4. S. Albers and M. Hellwig. Semi-online scheduling revisited. Theoretical Computer Science, 443:1-9, 2012. Publisher: Elsevier. Google Scholar
  5. S. Albers and M. Hellwig. Online makespan minimization with parallel schedules. Algorithmica, 78(2):492-520, 2017. Publisher: Springer. Google Scholar
  6. S. Albers and M. Janke. Scheduling in the Random-Order Model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). unpublished, 2020. Google Scholar
  7. S. Albers and L. Ladewig. New results for the k-secretary problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.00488.
  8. Pablo Azar, Robert Kleinberg, and S. Weinberg. Prophet inequalities with limited information. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, July 2013. URL: https://doi.org/10.1137/1.9781611973402.100.
  9. M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. Matroid Secretary Problems. Journal of the ACM (JACM), 65(6):1-26, 2018. Publisher: ACM New York, NY, USA. Google Scholar
  10. M. Babaioff, N. Immorlica, D. Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, pages 16-28. Springer, 2007. Google Scholar
  11. Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 51-58, 1992. Google Scholar
  12. Y. Bartal, H. J. Karloff, and Y. Rabani. A better lower bound for on-line scheduling. Inf. Process. Lett., 50(3):113-116, 1994. Google Scholar
  13. Martin Böhm, Jiří Sgall, Rob Van Stee, and Pavel Vesely. A two-phase algorithm for bin stretching with stretching factor 1.5. Journal of Combinatorial Optimization, 34(3):810-828, 2017. Google Scholar
  14. B. Chen, A. van Vliet, and G. J. Woeginger. A lower bound for randomized on-line scheduling algorithms. Information Processing Letters, 51(5):219-222, 1994. Publisher: Elsevier. Google Scholar
  15. L. Chen, D. Ye, and G. Zhang. Approximating the optimal algorithm for online scheduling problems via dynamic programming. Asia-Pacific Journal of Operational Research, 32(01):1540011, 2015. Publisher: World Scientific. Google Scholar
  16. T.C.E. Cheng, H. Kellerer, and V. Kotov. Semi-on-line multiprocessor scheduling with given total processing time. Theoretical computer science, 337(1-3):134-146, 2005. Publisher: Elsevier. Google Scholar
  17. J. Correa, A. Cristi, B. Epstein, and J. Soto. The two-sided game of googol and sample-based prophet inequalities. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2066-2081. SIAM, 2020. Google Scholar
  18. J. Correa, A. Cristi, L. Feuilloley, T. Oosterwijk, and A. Tsigonias-Dimitriadis. The secretary problem with independent sampling. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2047-2058. SIAM, 2021. Google Scholar
  19. J. Correa, P. Dütting, F. Fischer, and K. Schewior. Prophet inequalities for iid random variables from an unknown distribution. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 3-17, 2019. Google Scholar
  20. J. Dohrau. Online makespan scheduling with sublinear advice. In International Conference on Current Trends in Theory and Practice of Informatics, pages 177-188. Springer, 2015. Google Scholar
  21. E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics, 4:627-629, 1963. Google Scholar
  22. M. Englert, D. Özmen, and M. Westermann. The power of reordering for online minimum makespan scheduling. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 603-612. IEEE, 2008. Google Scholar
  23. U. Faigle, W. Kern, and G. Turán. On the performance of on-line algorithms for partition problems. Acta cybernetica, 9(2):107-119, 1989. Google Scholar
  24. M. Feldman, O. Svensson, and R. Zenklusen. A simple O (log log (rank))-competitive algorithm for the matroid secretary problem. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1189-1201. SIAM, 2014. Google Scholar
  25. T. S. Ferguson. Who solved the secretary problem? Statistical science, 4(3):282-289, 1989. Publisher: Institute of Mathematical Statistics. Google Scholar
  26. R. Fleischer and M. Wahl. On-line scheduling revisited. Journal of Scheduling, 3(6):343-353, 2000. Publisher: Wiley Online Library. Google Scholar
  27. G. Galambos and G. J. Woeginger. An on-line scheduling heuristic with better worst-case ratio than Graham’s list scheduling. SIAM Journal on Computing, 22(2):349-355, 1993. Publisher: SIAM. Google Scholar
  28. O. Göbel, T. Kesselheim, and A. Tönnis. Online appointment scheduling in the random order model. In Algorithms-ESA 2015, pages 680-692. Springer, 2015. Google Scholar
  29. G. Goel and A. Mehta. Online budgeted matching in random input models with applications to Adwords. In SODA, volume 8, pages 982-991, 2008. Google Scholar
  30. T. Gormley, N. Reingold, E. Torng, and J. Westbrook. Generating adversaries for request-answer games. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 564-565, 2000. Google Scholar
  31. R. L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9):1563-1581, 1966. Publisher: Wiley Online Library. Google Scholar
  32. A. Gupta, R. Mehta, and M. Molinaro. Maximizing Profit with Convex Costs in the Random-order Model. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.08172.
  33. A. Gupta and S. Singla. Random-order models. In Tim Roughgarden, editor, Beyond worst-case analysis. Cambridge University Press, 2020. Google Scholar
  34. D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM (JACM), 34(1):144-162, 1987. Publisher: ACM New York, NY, USA. Google Scholar
  35. H. Kaplan, D. Naori, and D. Raz. Competitive Analysis with a Sample and the Secretary Problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2082-2095. SIAM, 2020. Google Scholar
  36. C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587-596, 2011. Google Scholar
  37. D. R. Karger, S. J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20(2):400-430, 1996. Publisher: Elsevier. Google Scholar
  38. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990. Google Scholar
  39. H. Kellerer and V. Kotov. An efficient algorithm for bin stretching. Operations Research Letters, 41(4):343-346, 2013. Publisher: Elsevier. Google Scholar
  40. H. Kellerer, V. Kotov, and M. Gabay. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. Journal of Scheduling, 18(6):623-630, 2015. Google Scholar
  41. H. Kellerer, V. Kotov, M. Grazia Speranza, and Z. Tuza. Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5):235-242, 1997. Publisher: Elsevier. Google Scholar
  42. C. Kenyon. Best-Fit Bin-Packing with Random Order. In SODA, volume 96, pages 359-364, 1996. Google Scholar
  43. T. Kesselheim, A. Tönnis, K. Radke, and B. Vöcking. Primal beats dual on online packing LPs in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 303-312, 2014. Google Scholar
  44. R. D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, volume 5, pages 630-631, 2005. Google Scholar
  45. N. Korula, V. Mirrokni, and M. Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. SIAM Journal on Computing, 47(3):1056-1086, 2018. Publisher: SIAM. Google Scholar
  46. O. Lachish. O (log log rank) competitive ratio for the matroid secretary problem. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 326-335. IEEE, 2014. Google Scholar
  47. D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society: Series C (Applied Statistics), 10(1):39-51, 1961. Publisher: Wiley Online Library. Google Scholar
  48. M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 597-606, 2011. Google Scholar
  49. A. Meyerson. Online facility location. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 426-431. IEEE, 2001. Google Scholar
  50. V.S. Mirrokni, S. O. Gharan, and M. Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1690-1701. SIAM, 2012. Google Scholar
  51. M. Molinaro. Online and random-order load balancing simultaneously. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1638-1650. SIAM, 2017. Google Scholar
  52. C. J. Osborn and E. Torng. List’s worst-average-case or WAC ratio. Journal of Scheduling, 11(3):213-215, 2008. Publisher: Springer. Google Scholar
  53. J. Rudin III. Improved bounds for the on-line scheduling problem. PhD thesis, University of Phoenix, 2001. Google Scholar
  54. P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Publisher: INFORMS. Google Scholar
  55. J. Sgall. A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters, 63(1):51-55, 1997. Publisher: Citeseer. Google Scholar
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