New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling

Interval scheduling is a basic algorithmic problem and a classical task in combinatorial optimization. We develop techniques for partitioning and grouping jobs based on their starting/ending times, enabling 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 a dynamic setting produces several new results. For \((1+\varepsilon )\) $(1+\epsilon )$ -approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with \(O(\nicefrac {\log {n}}{\varepsilon })\) $O(\raisebox{1ex}{$logn$}\!\left/ \!\raisebox{-1ex}{$\epsilon $}\right.)$ update and \(O(\log {n})\) $O(logn)$ query worst-case time. Our techniques are also applicable in a setting where jobs have weights. We design a fully dynamic deterministic algorithm whose worst-case update and query times are \(\text {poly} (\log n,\frac{1}{\varepsilon })\) $\text{poly}(logn,\frac{1}{\epsilon })$ . This is the first algorithm that maintains a \((1+\varepsilon )\) $(1+\epsilon )$ -approximation of the maximum independent set of a collection of weighted intervals in \(\text {poly} (\log n,\frac{1}{\varepsilon })\) $\text{poly}(logn,\frac{1}{\epsilon })$ time updates/queries. This is an exponential improvement in \(1/\varepsilon \) $1/\epsilon$ over the running time of an algorithm of Henzinger, Neumann, and Wiese  [SoCG, 2020]. Our approach also removes all dependence on the values of the jobs’ starting/ending times and weights.