@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}, publisher = {EDP-Sciences}, volume = {42}, number = {2}, year = {2008}, pages = {237-252}, doi = {10.1051/ita:2007032}, zbl = {1147.68869}, mrnumber = {2401260}, language = {en}, url = {http://www.numdam.org/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) no. 2, pp. 237-252. doi : 10.1051/ita:2007032. http://www.numdam.org/item/ITA_2008__42_2_237_0/

[1] Improved parallel approximation of a class of integer programming problems. Algorithmica 17 (1997) 449-462. | MR 1429214 | Zbl 0869.68054

, and ,[2] 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

, , and ,[3] 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

, , and ,[4] Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58 (1999) 193-210. | MR 1688590 | Zbl 0937.68160

, , and ,[5] Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. (1979). | MR 519066 | Zbl 0411.68039

, and ,[6] Using quadratic programming to solve high multiplicity scheduling problems on parallel machines. Algorithmica 17 (1997) 100-110. | MR 1425728 | Zbl 0865.68008

, , and ,[7] Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995). | MR 1333600 | Zbl 0829.68068

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

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

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

, , and ,[11] 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

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

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

,[14] Randomized Algorithms. Cambridge University Press (1995). | MR 1344451 | Zbl 0849.68039

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

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

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

,[18] The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci. 259 (2001) 217-231. | MR 1832792 | Zbl 1142.90452

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

, and ,[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] The approximability of non-boolean satisfiability problems and restricted integer programming. Theoret. Comput. Sci. 332 (2005) 123-139. | MR 2122500 | Zbl 1070.68156

, , and ,