Parallel approximation to high multiplicity scheduling problems V I A smooth multi-valued quadratic programming

Maria Serna; Fatos Xhafa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2008)

  • Volume: 42, Issue: 2, page 237-252
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Serna, Maria, and 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 42.2 (2008): 237-252. <http://eudml.org/doc/245498>.

@article{Serna2008,
abstract = {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.},
author = {Serna, Maria, Xhafa, Fatos},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {parallel approximation; quadratic programming; multiplicity scheduling problem},
language = {eng},
number = {2},
pages = {237-252},
publisher = {EDP-Sciences},
title = {Parallel approximation to high multiplicity scheduling problems $VIA$ smooth multi-valued quadratic programming},
url = {http://eudml.org/doc/245498},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Serna, Maria
AU - Xhafa, Fatos
TI - Parallel approximation to high multiplicity scheduling problems $VIA$ smooth multi-valued quadratic programming
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2008
PB - EDP-Sciences
VL - 42
IS - 2
SP - 237
EP - 252
AB - 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.
LA - eng
KW - parallel approximation; quadratic programming; multiplicity scheduling problem
UR - http://eudml.org/doc/245498
ER -

References

top
  1. [1] N. Alon, and A. Srinivasan, Improved parallel approximation of a class of integer programming problems. Algorithmica 17 (1997) 449–462. Zbl0869.68054MR1429214
  2. [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. Zbl0968.68534MR1688590
  3. [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. Zbl1154.90602MR1450599
  4. [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. Zbl0937.68160MR1688590
  5. [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). Zbl0411.68039MR519066
  6. [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. Zbl0865.68008MR1425728
  7. [7] R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995). Zbl0829.68068MR1333600
  8. [8] D.S. Hochbaum, and R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. RAIRO Oper. Res. 39 (1991) 648–653. Zbl0736.90043
  9. [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. [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. [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. Zbl0896.68078MR1613003
  12. [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. Zbl1310.68224
  13. [13] M. Minoux, Mathematical programming: theory and algorithms, Wiley (1986). Zbl0602.90090MR868279
  14. [14] R. Motwani, and P. Raghavan, Randomized Algorithms. Cambridge University Press (1995). Zbl0849.68039MR1344451
  15. [15] P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37 (1988) 130–143. Zbl0659.90066MR979115
  16. [16] P. Raghavan, and C. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7 (1987) 365–374. Zbl0651.90052MR931194
  17. [17] M. Serna, Approximating linear programming is logspace complete for P. Inform. Process. Lett. 37 (1991) 233–236. Zbl0713.90046MR1095711
  18. [18] M. Serna, and F. Xhafa, The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci. 259 (2001) 217–231. Zbl1142.90452MR1832792
  19. [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. [20] L. Trevisan, Luca Trevisan: Positive linear programming, parallel approximation and PCP’s. Lect. Notes Comput. Sci. 1136 (1996) 62–75. Zbl1100.68031MR1469227
  21. [21] L. Trevisan, Parallel approximation algorithms by positive linear programming. Algorithmica 21 (1998) 72–88. Zbl0896.68072MR1612219
  22. [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. Zbl1070.68156MR2122500

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.