Dorit S. Hochbaum
Abstract
The problem of scheduling a set of n jobs on 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 O((n/ε)1/ε2) and has relative error at most ε is given. In addition, more practical algorithms for ε = 1/5 + 2-k and ε = 1/6 + 2-k, which have running times O(n(k + log n)) and O(n(km4 + log 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.
- 1 COFFMAN, JR, E. G., GAREY, M. R., AND JOHNSON, D. S. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7 (1978), 1-17.Google Scholar
- 2 FERNANDEZ DE Lk VEGA, W., AND LUEKER, G.S. Bin packing can be solved within 1 + ~ in linear time. Combinatorica I (1981), 349-355.Google Scholar
- 3 FRIESEN, D. K. Sensitivity analysis for heuristic algorithms. Tech. Rep. UIUCDCS-R-78-939, Department of Computer Science, Univ. of Illinois, Urbana-Champaign, 1978.Google Scholar
- 4 FRIESEN, D.K. Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput. 13 (1984), 170-181.Google Scholar
- 5 GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability. A Guide to the Theory of NP-Comp/eteness. Freeman, San Francisco, 1979. Google Scholar
- 6 GRAHAM, R. L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45 (1966), 1563-1581.Google Scholar
- 7 GRAHAM, R.L. Bounds on multiprocessing timing anomalies. SIAM J~ Appl. Math. 17 (1969), 263-269.Google Scholar
- 8 HOCHBAUM, D. S., AND SHMOVS, D.B. A bin packing problem you can almost solve by sitting on your suitcase. SIAM J. Algebraic Discrete Methods 7 (1986), 247-257. Google Scholar
- 9 IBARRA, O. H., AND KIM, C.E. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 4 (Oct. 1975), 463-468. Google Scholar
- 10 KARMARKAR, N., AND KARP, R.M. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 312-320.Google Scholar
- 11 LANGSTON, M.A. Processor scheduling with improved heuristic algorithms. Doctoral dissertation, Texas A&M Univ., College Station, Tex., 1981. Google Scholar
- 12 LAWLER, E.L. Fast approximation algorithms for knapsack problems. In Proceedings of the 18th IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 1977, pp. 206-213.Google Scholar
- 13 SAHNI, S.K. Algorithms for scheduling independent tasks. J. ACM 23 1 (Jan. 1976), i 16-127. Google Scholar
Index Terms
- Using dual approximation algorithms for scheduling problems theoretical and practical results
Recommendations
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph $$G = (V, E)$$G=(V,E) is a subset $$S\subseteq V$$S⊆V of vertices ...
Comments