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

URL stable : http://www.numdam.org/item?id=ITA_2008__42_2_237_0

Classification: 68W10, 68W25, 90B35, 90C20

### Bibliographie

[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 ,