Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: New Partitioning Techniques and Faster Algorithms for Approximate
  Interval Scheduling   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 obtain 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. Our techniques are also applicable in
a setting where jobs have rewards/weights. For this case we obtain a fully
dynamic algorithm whose worst-case update and query time has only polynomial
dependence on $1/\varepsilon$, which is an exponential improvement over the
result of Henzinger et al. [SoCG, 2020].
  We extend our approaches for interval scheduling on a single machine to the
setting with $M$ machines. In one method of extension, we achieve similar
approximation factors at the expense of a slower update time in the dynamic
setting. In our other method of extension, we provide a general framework for
reducing the task of interval scheduling on $M$ machines to that of interval
scheduling on a single machine without any slow-down. In the unweighted case
this reduction approach incurs an additional multiplicative approximation
factor of $2 - 1/M$ in expectation, while in the weighted case this incurs a
multiplicative approximation factor of $e$ in expectation.

23
The categories of this paper are: solv-int
2
The categories of this paper are: math
5
The categories of this paper are: gr-qc
15
The categories of this paper are: nucl-ex
7
The categories of this paper are: hep-th
33
The categories of this paper are: plasm-ph
25
The categories of this paper are: patt-sol
3
The categories of this paper are: physics
24
The categories of this paper are: dg-ga
37
The categories of this paper are: supr-con
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
22
The categories of this paper are: chao-dyn
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
11
The categories of this paper are: hep-lat