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.
@article{ITA_2008__42_2_237_0,
author = {Serna, Maria and Xhafa, Fatos},
title = {Parallel approximation to high multiplicity scheduling problems via smooth multi-valued quadratic programming},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {42},
year = {2008},
pages = {237-252},
doi = {10.1051/ita:2007032},
mrnumber = {2401260},
zbl = {1147.68869},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2008__42_2_237_0}
}
Serna, Maria; Xhafa, Fatos. Parallel approximation to high multiplicity scheduling problems via smooth multi-valued quadratic programming. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 237-252. doi : 10.1051/ita:2007032. http://gdmltest.u-ga.fr/item/ITA_2008__42_2_237_0/
[1] , and , Improved parallel approximation of a class of integer programming problems. Algorithmica 17 (1997) 449-462. | MR 1429214 | Zbl 0869.68054
[2] , , and , 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 1688590 | Zbl 0968.68534
[3] , , and , 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 1450599
[4] , , and , Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58 (1999) 193-210. | MR 1688590 | Zbl 0937.68160
[5] , and , Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. (1979). | MR 519066 | Zbl 0411.68039
[6] , , and , Using quadratic programming to solve high multiplicity scheduling problems on parallel machines. Algorithmica 17 (1997) 100-110. | MR 1425728 | Zbl 0865.68008
[7] , , and , Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995). | MR 1333600 | Zbl 0829.68068
[8] , and , Strongly polynomial algorithms for the high multiplicity scheduling problem. RAIRO Oper. Res. 39 (1991) 648-653. | Zbl 0736.90043
[9] , , and , An approximation algorithm for the bandwidth problem on dense graphs. Technical Report TR97-017, ECCC (1997).
[10] , , and , Polynomial times approximation schemes for some dense instances of NP-hard problems. Technical Report TR97-024, ECCC (1997).
[11] , and , Approximating dense cases of covering problems. Network design: connectivity and facilities location (Princeton, NJ, 1997). Amer. Math. Soc. (1998) 169-178. | MR 1613003 | Zbl 0896.68078
[12] , and , A parallel approximation algorithm for positive linear programming, in Proceedings of 25th ACM Symposium on Theory of Computing (1993) 448-457.
[13] , Mathematical programming: theory and algorithms, Wiley (1986). | MR 868279 | Zbl 0602.90090
[14] , and , Randomized Algorithms. Cambridge University Press (1995). | MR 1344451 | Zbl 0849.68039
[15] , Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988) 130-143. | MR 979115 | Zbl 0659.90066
[16] , and , Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) 365-374. | MR 931194 | Zbl 0651.90052
[17] , Approximating linear programming is logspace complete for P. Inform. Process. Lett. 37 (1991) 233-236. | MR 1095711 | Zbl 0713.90046
[18] , and , The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci. 259 (2001) 217-231. | MR 1832792 | Zbl 1142.90452
[19] , and , Fast, parallel and sequential approximations to “hard” combinatorial optimization problems. Technical Report TR99/06/01, CTI, Patras (June 1999).
[20] , : Positive linear programming, parallel approximation and PCP's. Lect. Notes Comput. Sci. 1136 (1996) 62-75. | MR 1469227
[21] , Parallel approximation algorithms by positive linear programming. Algorithmica 21 (1998) 72-88. | MR 1612219 | Zbl 0896.68072
[22] , , and , The approximability of non-boolean satisfiability problems and restricted integer programming. Theoret. Comput. Sci. 332 (2005) 123-139. | MR 2122500 | Zbl 1070.68156