License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.67
URN: urn:nbn:de:0030-drops-164086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16408/
Gawrychowski, Paweł ;
Pokorski, Karol
Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)
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.
BibTeX - Entry
@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2022.67,
author = {Gawrychowski, Pawe{\l} and Pokorski, Karol},
title = {{Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {67:1--67:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16408},
URN = {urn:nbn:de:0030-drops-164086},
doi = {10.4230/LIPIcs.ICALP.2022.67},
annote = {Keywords: interval scheduling, dynamic problems, data structures, greedy algorithms}
}
|
Keywords: |
|
interval scheduling, dynamic problems, data structures, greedy algorithms |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
