On the optimality of approximation schemes for the classical scheduling problem

DOI10.1137/1.9781611973402.50MaRDI QIDQ5384011zbMATH OpenOpenAlexFDO

Authors Lin Chen, Klaus Jansen, Guochuan Zhang

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0398

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Abstract: We consider the classical scheduling problem on parallel identical machines to minimize the makespan, and achieve the following results under the Exponential Time Hypothesis (ETH) 1. The scheduling problem on a constant number $m$ of identical machines, which is denoted as $Pm||C_{max}$, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time $O(n)+(1/epsilon{)}^{O(m)}$ (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a $(1/epsilon{)}^{O(m^{1-delta})}+n^{O(1)}$ time FPTAS for any $delta>0$ implies that ETH fails. 2. The scheduling problem on an arbitrary number of identical machines, which is denoted as $P||C_{max}$, is known to admit a polynomial time approximation scheme (PTAS) of running time $2^{O(1/epsilo{n}^{2}lo{g}^3(1/epsilon))}+n^{O(1)}$. We prove this algorithm is nearly optimal in the sense that a $2^{O((1/epsilon{)}^{1-delta})}+n^{O(1)}$ time PTAS for any $delta>0$ implies that ETH fails, leaving a small room for improvement. To obtain these results we will provide two new reductions from 3SAT, one for $Pm||C_{max}$ and another for $P||C_{max}$. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for $P||C_{max}$, Chen et al. (arXiv:1306.3727) is able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times $P=(p_{ij}{)}_{mimesn}$ is of rank 3, solving the open problem mentioned by Bhaskara et al. (SODA 2013).

Recommendations

• On the optimality of exact and approximation algorithms for scheduling problems
• scientific article; zbMATH DE number 6820261
• Approximability of scheduling with fixed jobs
• Closing the gap for makespan scheduling via sparsification techniques
• Approximation algorithms for scheduling unrelated parallel machines

Cited in

(24)

• On the optimality of exact and approximation algorithms for scheduling problems
• FPT approximation algorithm for scheduling with memory constraints
• Vector scheduling with rejection on a single machine
• An improved lower bound for rank four scheduling
• Approximability of scheduling with fixed jobs
• A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay
• Scheduling lower bounds via AND subset sum
• The piggyback transportation problem: transporting drones launched from a flying warehouse
• Precedence scheduling with unit execution time is equivalent to parametrized biclique
• Closing the gap for makespan scheduling via sparsification techniques
• scientific article; zbMATH DE number 3908144 (Why is no real title available?)
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Closing the Gap for Pseudo-Polynomial Strip Packing
• Minimum makespan scheduling with low rank processing times
• Bounding the running time of algorithms for scheduling and packing problems
• Bounding the running time of algorithms for scheduling and packing problems
• Streaming algorithms for bin packing and vector scheduling
• On the complexity of scheduling problems with a fixed number of parallel identical machines
• Scheduling with machine conflicts
• An efficient PTAS for stochastic load balancing with Poisson jobs
• On the computational complexity of (maximum) shift class scheduling
• Scheduling with locality by routing
• Approximation schemes for multiprocessor scheduling within budget
• Necessary and sufficient conditions of optimality for some classical scheduling problems

This page was built for publication: On the optimality of approximation schemes for the classical scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384011)