Abstract
We show how to approximate in NC the problem of Scheduling Unrelated Parallel Machines, for a fixed number of machines. We develop a (2 + ε)-approximate parallel algorithm for the problem. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The relationship established enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. Finally, we show that the same technique can be applied to the General Assignment Problem of fixed number of machines and a given makespan T, thus yielding a schedule whose cost is at most (2 + ε) times the minimum cost and has makespan at most 2T.
This research was partially supported by the ESPRIT Long Term Research Project No. 20244 - ALCOM IT.
Chapter PDF
Similar content being viewed by others
References
Berger, B. and Rompel, J.: Simulating (logc n)-wise Independence in NC. J. of the ACM, 38 (1991) 1026–1046
Dobkin, D., Lipton, J.R. and Reiss, S.: Linear Programming is Logspace Hard for P. IPL, 8 (1979) 96–97
Goemans, M.X. and Williamson, D.P.: New 3/4-approximation Algorithms for the Maximum Satisfability Problem. SIAM J. Disc. Math., 7 (1994) 656–666
Hall, L.A.: Approximability of Flow Shop Scheduling. In Proc. of 36th IEEE Symp. on Found. of Comp. Sc, (1995) 82-91
Hochbaum, D.S.: Approximation Algorithms for the Set Cover and the Vertex Cover. SIAM J. of Comp., 11(3) (1982) 555–556
Horowitz, E. and Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM, 23 (1976) 317–327
Karp, R.M.: Reducibility Among Combinatorial Problems. Complexity of Computer Computations, eds. R.E. Miller and J.W. Thatcher, Plenum Press, 1972.
Khachyan, L.G.: A Polynomial Algorithm in Linear Programming. Trans. in Sov. Math. Dok., 20 (1979) 191–194
Lenstra, J.K., Shmoys, D.B. and Tardos, É.: Approximation Algorithms for Scheduling Unrelated Parallel Machines. Math. Prog., 46 (1990) 259–271
Luby, M.: Removing Randomness in Parallel Computation without a Processor Penalty. In Proc. of 29th IEEE Symp. on Found. of Comp. Sci., (1988) 162–173
Luby, M. and Nisan, N.: A Parallel Approximation Algorithm for Positive Linear Programming. In Proc. of 25th ACM Symp. on Th. of Comp., (1993) 448–457
Megiddo, N.: A Note on Approximate Linear Programming. IPL, 42 (1992) 53
Motwani, R. and Naor, J.S. and Naor, M.: The Probabilistic Method Yields Deterministic Parallel Algorithms. J. of Comp. and Sys. Sci., 49 (1994) 478–516
Potts, C.N.: Analysis of a Linear Programming Heuristic for Scheduling Unrelated Parallel Machines. Disc. App. Math., 10 (1985) 155–164
Raghavan, R. and Thompson, C.: Randomized Rounding: a Technique for Provably Good Algorithms and Algorithmic Proofs. Combinatorica, 7 (1987) 365–374
Serna, M.J.: Approximating Linear Programming is Logspace Complete for P. IPL, 37 (1991) 233–236
Shmoys, D.B. and Tardos, É.: An Approximation Algorithms for the Generalized Assignment Problem. Math. Prog., 62 (1993) 461–474
Trevisan, L.: Positive Linear Programming, Parallel Approximation and PCP's. ESA'96, LNCS 1136 (1996) 62–75
Trevisan, L. and Xhafa, F.: The Parallel Complexity of Positive Linear Programming. Tech. Rep. Dept. of LSI, (1996) LSI-96-52-R
Walukiewicz, S.: Integer Programming, Kluwer Acad. Publ., (1990)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Serna, M., Xhafa, F. (1997). Approximating scheduling problems in parallel. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002768
Download citation
DOI: https://doi.org/10.1007/BFb0002768
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.