论文标题
新的分区技术和更快的算法，用于近似间隔时间表
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
论文作者
论文摘要
间隔调度是算法理论和组合优化的经典任务中的一个基本问题。我们开发了一组技术，用于根据他们的开始和结束时间进行分区和分组工作，这使我们能够将许多作业的间隔计划视为多个间隔调度实例的结合，每个实例仅包含少数几个工作。在计算的动态和本地设置中实例化这些技术会导致几个新结果。 对于$（1+ \ varepsilon）$ - 单台计算机上$ n $ jobs的作业计划的近似，我们使用$ O（\ frac {\ frac {\ log {n}} {\ varepsilon} {\ varepsilon}）$ o（\ frac {\ frac {\ log {n}}）$（\ log o（log log {n}）$ query worst-case time。此外，我们设计了一种本地计算算法，该算法仅使用$ o（\ frac {\ log {n}}} {\ varepsilon}）$查询当所有作业的长度至少$ 1 $，并且在$ [0，n] $之内都有启动/结束时间。我们的技术也适用于作业具有奖励/权重的环境。在这种情况下，我们设计了一种完全动态的确定性算法，其最差的更新和查询时间是$ \ permatatorName {poly}（\ log n，\ frac {1} {\ varepsilon}）$。同等地，这是第一种维护$（1+ \ varepsilon）$的算法 - 在$ \ operatorname {poly n，\ log n，\ frac {1} {\ varepsilon} {\ varepsilon} {\ varepsilon} {\ varepsilon} {\ varepsilon} {\ varepsilon}）$ time time time time time time更新中的加权间隔集合的最大独立集近似。这是$ 1/\ varepsilon $的指数改善，在Henzinger，Neumann和Wiese〜 [SocG，2020年]的随机算法的运行时间内，同时还取消了所有依赖工作的启动/终点时间和奖励值的价值，以及是否需要任何随机性。 我们还扩展了在单台计算机上进行间隔调度的方法，以使用$ M $机器检查设置。
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+\varepsilon)$-approximation of job scheduling of $n$ jobs on a single machine, we develop a fully dynamic algorithm with $O(\frac{\log{n}}{\varepsilon})$ update and $O(\log{n})$ query worst-case time. Further, we design a local computation algorithm that uses only $O(\frac{\log{N}}{\varepsilon})$ 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 $\operatorname{poly}(\log n,\frac{1}{\varepsilon})$. Equivalently, this is the first algorithm that maintains a $(1+\varepsilon)$-approximation of the maximum independent set of a collection of weighted intervals in $\operatorname{poly}(\log n,\frac{1}{\varepsilon})$ time updates/queries. This is an exponential improvement in $1/\varepsilon$ 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.
