2026-07-24T00:04:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18097 2024-03-06T11:01:00Z ddc:004 open_access

New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling Compton, Spencer Mitrović, Slobodan Rubinfeld, Ronitt interval scheduling dynamic algorithms local computation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Spencer Compton and Slobodan Mitrović and Ronitt Rubinfeld 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.45 urn:nbn:de:0030-drops-180978 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.45 eng https://creativecommons.org/licenses/by/4.0/legalcode