On the optimality of approximation schemes for the classical scheduling problem

Lin Chen, Klaus Jansen, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Scopus citations

Abstract

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: The scheduling problem on a constant number m of identical machines, which is denoted as Pm||Cmax, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O(n) + (1/ε)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/ε)O(m1-δ) +n O(1) time FPTAS for any δ > 0 implies that ETH fails. The scheduling problem on an arbitrary number of identical machines, which is denoted as P||Cmax is known to admit a polynomial time approximation scheme (PTAS) of running time 2O{1/e2log3(1/ε)+n O(1) We prove this algorithm is nearly optimal in the sense that a 2 O((1/ε)1-δ) + nO(1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: The traditional dynamic programming algorithm for P||Cmax is known to run in 2O(n) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O(n), an exact algorithm of running time 2O(n1-δ) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for Pm||Cmax 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||Cmax, Chen et al. [5] are able to prove the APX- hardness of the scheduling problem in which the matrix of job processing times P = (pij)m×n is of rank 3, solving the open problem mentioned in [2].

Original languageEnglish
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages657-668
Number of pages12
ISBN (Print)9781611973389
DOIs
StatePublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR
Period01/5/1401/7/14

Fingerprint

Dive into the research topics of 'On the optimality of approximation schemes for the classical scheduling problem'. Together they form a unique fingerprint.

Cite this