Document Open Access Logo

Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)

Authors Paweł Gawrychowski, Karol Pokorski

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.67.pdf
  • Filesize: 0.97 MB
  • 19 pages

Document Identifiers

Author Details

Paweł Gawrychowski
  • Institute of Computer Science, University of Wrocław, Poland
Karol Pokorski
  • Institute of Computer Science, University of Wrocław, Poland

Cite AsGet BibTex

Paweł Gawrychowski and Karol Pokorski. Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.67

Abstract

We revisit the complexity of the classical Interval Scheduling in the dynamic setting. In this problem, the goal is to maintain a set of intervals under insertions and deletions and report the size of the maximum size subset of pairwise disjoint intervals after each update. Nontrivial approximation algorithms are known for this problem, for both the unweighted and weighted versions [Henzinger, Neumann, Wiese, SoCG 2020]. Surprisingly, it was not known if the general exact version admits an exact solution working in sublinear time, that is, without recomputing the answer after each update. Our first contribution is a structure for Dynamic Interval Scheduling with amortized 𝒪̃(n^{1/3}) update time. Then, building on the ideas used for the case of one machine, we design a sublinear solution for any constant number of machines: we describe a structure for Dynamic Interval Scheduling on m ≥ 2 machines with amortized 𝒪̃(n^{1 - 1/m}) update time. We complement the above results by considering Dynamic Weighted Interval Scheduling on one machine, that is maintaining (the weight of) the maximum weight subset of pairwise disjoint intervals. We show an almost linear lower bound (conditioned on the hardness of Minimum Weight k-Clique) for the update/query time of any structure for this problem. Hence, in the weighted case one should indeed seek approximate solutions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • interval scheduling
  • dynamic problems
  • data structures
  • greedy algorithms

Metrics

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

Related Versions

References

  1. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, October 2005. URL: https://doi.org/10.1145/1103963.1103966.
  2. Amihood Amir and Itai Boneh. Dynamic suffix array with sub-linear update time and poly-logarithmic lookup time. CoRR, abs/2112.12678, 2021. Google Scholar
  3. Esther M. Arkin and Ellen B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1):1-8, 1987. URL: https://doi.org/10.1016/0166-218X(87)90037-0.
  4. Michael A Bender, Richard Cole, Erik D Demaine, Martin Farach-Colton, and Jack Zito. Two simplified algorithms for maintaining order in a list. In European Symposium on Algorithms, pages 152-164. Springer, 2002. Google Scholar
  5. Khalid I. Bouzina and Hamilton Emmons. Interval scheduling on identical machines. Journal of Global Optimization, 9(3):379-393, December 1996. URL: https://doi.org/10.1007/BF00121680.
  6. Martin C. Carlisle and Errol L. Lloyd. On the k-coloring of intervals. Discrete Applied Mathematics, 59(3):225-235, 1995. URL: https://doi.org/10.1016/0166-218X(95)80003-M.
  7. Spencer Compton, Slobodan Mitrović, and Ronitt Rubinfeld. New partitioning techniques and faster algorithms for approximate interval scheduling, 2020. URL: http://arxiv.org/abs/2012.15002.
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  9. P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 365-372, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.28434.
  10. Christof Doll, Tanja Hartmann, and Dorothea Wagner. Fully-dynamic hierarchical graph clustering using cut trees. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, pages 338-349, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  11. Ulrich Faigle and Willem M. Nawijn. Note on scheduling intervals on-line. Discrete Applied Mathematics, 58(1):13-17, 1995. URL: https://doi.org/10.1016/0166-218X(95)00112-5.
  12. Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, and Jiamou Liu. Dynamic algorithms for monotonic interval scheduling problem. Theoretical Computer Science, 562:227-242, 2015. URL: https://doi.org/10.1016/j.tcs.2014.09.046.
  13. Pawel Gawrychowski and Wojciech Janczewski. Fully dynamic approximation of LIS in polylogarithmic time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 654-667. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451137.
  14. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21-30. ACM, 2015. Google Scholar
  15. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1-51:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
  16. Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, July 1999. URL: https://doi.org/10.1145/320211.320215.
  17. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, July 2001. URL: https://doi.org/10.1145/502090.502095.
  18. Dominik Kempa and Tomasz Kociumaka. Dynamic suffix array with polylogarithmic queries and updates. CoRR, abs/2201.01285, 2022. URL: http://arxiv.org/abs/2201.01285.
  19. Jon Kleinberg and Eva Tardos. Algorithm Design. Addison Wesley, January 2006. Google Scholar
  20. Tomasz Kociumaka and Saeed Seddighin. Improved dynamic algorithms for longest increasing subsequence. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 640-653, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451026.
  21. Antoon W.J. Kolen, Jan Karel Lenstra, Christos H. Papadimitriou, and Frits C.R. Spieksma. Interval scheduling: A survey. Naval Research Logistics (NRL), 54(5):530-543, 2007. URL: https://doi.org/10.1002/nav.20231.
  22. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs, pages 1236-1252. Society for Industrial and Applied Mathematics, 2018. URL: https://doi.org/10.1137/1.9781611975031.80.
  23. Mihai Patrascu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35(4):932-963, 2006. URL: https://doi.org/10.1137/S0097539705447256.
  24. Dan E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N). Information Processing Letters, 17(2):81-84, 1983. URL: https://doi.org/10.1016/0020-0190(83)90075-3.
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 Imprint Privacy Contact