arXiv preprint ·
An EPTAS for Offline Temporary Tasks Assignment on Few Machines
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In offline temporary tasks assignment, each job has a time interval and a positive weight and is assigned to one of $r$ identical machines for its entire interval; the goal is to minimize the peak load, the largest total weight of jobs that are simultaneously active on one machine. For every fixed $r$, we give an efficient polynomial-time approximation scheme (EPTAS) with running time $f(r,1/\varepsilon)\cdot N^{O(1)}$, where $N$ is the input length. The previous approximation scheme, by Azar, Regev, Sgall, and Woeginger (2002), runs in time $n^{O(r^3\log r/\varepsilon^3)}$ on $n$ jobs. We also show that for every fixed $r\ge2$ the problem is strongly NP-hard, so it has no FPTAS unless P=NP, and that under the Exponential Time Hypothesis no deterministic $(1+\varepsilon)$-approximation runs in time $2^{o(1/\varepsilon)}\cdot N^{O(1)}$. The key idea is to bound the loads of each group of simultaneously active jobs by a few weighted intervals whose positions are fixed in advance; a dynamic program over the time line then only has to record which machine carries each interval.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective
Depth-Optimal Quantum Compilation
A 51-Addition Alternative-Basis Kernel for Rank-23 $3\times3$ Matrix Multiplication
Computational Complexity of Clifford Template Compilation: Are Quantum Computers Useful for Compiling Quantum Circuits?
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.