### Using dual approximation algorithms for scheduling problems theoretical and practical resultsUsing dual approximation algorithms for scheduling problems theoretical and practical results

Access Restriction
Subscribed

 Author Hochbaum, Dorit S. ♦ Shmoys, David B. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1987 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The problem of scheduling a set of $\textit{n}$ jobs on $\textit{m}$ identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization problems. In this paper the strongest possible type of result for this problem, a polynomial approximation scheme, is presented. More precisely, for each ε, an algorithm that runs in time $\textit{O}((\textit{n}/ε)1/ε2)$ and has relative error at most ε is given. In addition, more practical algorithms for ε = 1/5 + $2-\textit{k}$ and ε = 1/6 + $2-\textit{k},$ which have running times $\textit{O}(\textit{n}(\textit{k}$ + log $\textit{n}))$ and $\textit{O}(\textit{n}(\textit{km}4$ + log $\textit{n}))$ are presented. The techniques of analysis used in proving these results are extremely simple, especially in comparison with the baroque weighting techniques used previously.The scheme is based on a new approach to constructing approximation algorithms, which is called dual approximation algorithms, where the aim is to find superoptimal, but infeasible, solutions, and the performance is measured by the degree of infeasibility allowed. This notion should find wide applicability in its own right and should be considered for any optimization problem where traditional approximation algorithms have been particularly elusive. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1987-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 34 Issue Number 1 Page Count 19 Starting Page 144 Ending Page 162

#### Open content in new tab

Source: ACM Digital Library