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

Maria Serna; Fatos Xhafa

RAIRO - Theoretical Informatics and Applications (2007)

  • 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 42.2 (2007): 237-252. <http://eudml.org/doc/92869>.

@article{Serna2007,
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},
keywords = {Parallel approximation; quadratic programming; multiplicity scheduling problem},
language = {eng},
month = {9},
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/92869},
volume = {42},
year = {2007},
}

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
DA - 2007/9//
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/92869
ER -

References

top
  1. N. Alon, and A. Srinivasan, Improved parallel approximation of a class of integer programming problems. Algorithmica17 (1997) 449–462.  
  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.  
  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.  
  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.  
  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).  
  6. F. Granot, J. Skorin-Kapov, and A. Tamir, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines. Algorithmica17 (1997) 100–110.  
  7. R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995).  
  8. D.S. Hochbaum, and R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. RAIRO Oper. Res.39 (1991) 648–653.  
  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.  
  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).  
  14. R. Motwani, and P. Raghavan, Randomized Algorithms. Cambridge University Press (1995).  
  15. P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci.37 (1988) 130–143.  
  16. P. Raghavan, and C. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica7 (1987) 365–374.  
  17. M. Serna, Approximating linear programming is logspace complete for P. Inform. Process. Lett.37 (1991) 233–236.  
  18. M. Serna, and F. Xhafa, The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci.259 (2001) 217–231.  
  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.  
  21. L. Trevisan, Parallel approximation algorithms by positive linear programming. Algorithmica21 (1998) 72–88.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.