Parallel approximation to high multiplicity scheduling problems via smooth multi-valued quadratic programming

Serna, Maria; Xhafa, Fatos

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 2, pp. 237-252.

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel approximablity of these problems, we show first a parallel additive approximation procedure to a subclass of multi-valued quadratic programming, called smooth multi-valued QP, which is defined by imposing certain restrictions on the coefficients of the instance. We use this procedure to obtain parallel approximation to dense instances of the two problems by observing that dense instances of these problems are instances of smooth multi-valued QP. The dense instances of the problems considered here are defined similarly as for other combinatorial problems in the literature. For such instances we can find in parallel a near optimal schedule. The definition of smooth multi-valued QP as well as the procedure for approximating it in parallel are of interest independently of the application to the scheduling problems considered in this paper.

[1] N. Alon, and A. Srinivasan, Improved parallel approximation of a class of integer programming problems. Algorithmica 17 (1997) 449-462. | MR | Zbl

[2] S. Arora, D. Karger, and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems. Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing (STOC '95) 58 (1995) 284-293, ACM Press. | MR | Zbl

[3] S. Arora, A. Frieze, and H. Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, in Procedings of the FOCS'96 (1996) 21-30. | MR

[4] S. Arora, D. Karger, and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58 (1999) 193-210. | MR | Zbl

[5] M.R. Garey, and D.S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. (1979). | MR | Zbl

[6] F. Granot, J. Skorin-Kapov, and A. Tamir, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines. Algorithmica 17 (1997) 100-110. | MR | Zbl

[7] R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995). | MR | Zbl

[8] D.S. Hochbaum, and R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. RAIRO Oper. Res. 39 (1991) 648-653. | Zbl

[9] M. Karpinski, J. Wirtgen, and A. Zelikovsky, An approximation algorithm for the bandwidth problem on dense graphs. Technical Report TR97-017, ECCC (1997).

[10] M. Karpinski, J. Wirtgen, and A. Zelikovsky, Polynomial times approximation schemes for some dense instances of NP-hard problems. Technical Report TR97-024, ECCC (1997).

[11] M. Karpinski, and A. Zelikovsky, Approximating dense cases of covering problems. Network design: connectivity and facilities location (Princeton, NJ, 1997). Amer. Math. Soc. (1998) 169-178. | MR | Zbl

[12] M. Luby, and N. Nisan, A parallel approximation algorithm for positive linear programming, in Proceedings of 25th ACM Symposium on Theory of Computing (1993) 448-457.

[13] M. Minoux, Mathematical programming: theory and algorithms, Wiley (1986). | MR | Zbl

[14] R. Motwani, and P. Raghavan, Randomized Algorithms. Cambridge University Press (1995). | MR | Zbl

[15] P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988) 130-143. | MR | Zbl

[16] P. Raghavan, and C. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) 365-374. | MR | Zbl

[17] M. Serna, Approximating linear programming is logspace complete for P. Inform. Process. Lett. 37 (1991) 233-236. | MR | Zbl

[18] M. Serna, and F. Xhafa, The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci. 259 (2001) 217-231. | MR | Zbl

[19] P.S. Efraimidis, and P.G. Spirakis, Fast, parallel and sequential approximations to “hard” combinatorial optimization problems. Technical Report TR99/06/01, CTI, Patras (June 1999).

[20] L. Trevisan, Luca Trevisan: Positive linear programming, parallel approximation and PCP's. Lect. Notes Comput. Sci. 1136 (1996) 62-75. | MR

[21] L. Trevisan, Parallel approximation algorithms by positive linear programming. Algorithmica 21 (1998) 72-88. | MR | Zbl

[22] M. Serna, L. Trevisan, and F. Xhafa, The approximability of non-boolean satisfiability problems and restricted integer programming. Theoret. Comput. Sci. 332 (2005) 123-139. | MR | Zbl