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.2023.45
URN: urn:nbn:de:0030-drops-180978
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18097/
Compton, Spencer ;
Mitrović, Slobodan ;
Rubinfeld, Ronitt
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
Abstract
Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results.
For (1+ε)-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O((log n)/ε) update and O(log n) query worst-case time. Further, we design a local computation algorithm that uses only O((log N)/ε) queries when all jobs are length at least 1 and have starting/ending times within [0,N]. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are poly(log n,1/ε). Equivalently, this is the first algorithm that maintains a (1+ε)-approximation of the maximum independent set of a collection of weighted intervals in poly(log n,1/ε) time updates/queries. This is an exponential improvement in 1/ε over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese [SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness.
We also extend our approaches for interval scheduling on a single machine to examine the setting with M machines.
BibTeX - Entry
@InProceedings{compton_et_al:LIPIcs.ICALP.2023.45,
author = {Compton, Spencer and Mitrovi\'{c}, Slobodan and Rubinfeld, Ronitt},
title = {{New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {45:1--45:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18097},
URN = {urn:nbn:de:0030-drops-180978},
doi = {10.4230/LIPIcs.ICALP.2023.45},
annote = {Keywords: interval scheduling, dynamic algorithms, local computation algorithms}
}
|
Keywords: |
|
interval scheduling, dynamic algorithms, local computation algorithms |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
