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

RAIRO - Theoretical Informatics and Applications (2007)

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

## Access Full Article

top## Abstract

top## How to cite

topSerna, 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- N. Alon, and A. Srinivasan, Improved parallel approximation of a class of integer programming problems. Algorithmica17 (1997) 449–462. Zbl0869.68054
- 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.68534
- 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.90602
- 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.68160
- 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.68039
- F. Granot, J. Skorin-Kapov, and A. Tamir, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines. Algorithmica17 (1997) 100–110. Zbl0865.68008
- R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995). Zbl0829.68068
- D.S. Hochbaum, and R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. RAIRO Oper. Res.39 (1991) 648–653. Zbl0736.90043
- M. Karpinski, J. Wirtgen, and A. Zelikovsky, An approximation algorithm for the bandwidth problem on dense graphs. Technical Report TR97-017, ECCC (1997).
- 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).
- 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.68078
- 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
- M. Minoux, Mathematical programming: theory and algorithms, Wiley (1986). Zbl0602.90090
- R. Motwani, and P. Raghavan, Randomized Algorithms. Cambridge University Press (1995). Zbl0849.68039
- P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci.37 (1988) 130–143. Zbl0659.90066
- P. Raghavan, and C. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica7 (1987) 365–374. Zbl0651.90052
- M. Serna, Approximating linear programming is logspace complete for P. Inform. Process. Lett.37 (1991) 233–236. Zbl0713.90046
- M. Serna, and F. Xhafa, The parallel approximability of a subclass of quadratic programming. Theoret. Comput. Sci.259 (2001) 217–231. Zbl1142.90452
- 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).
- L. Trevisan, Luca Trevisan: Positive linear programming, parallel approximation and PCP's. Lect. Notes Comput. Sci.1136 (1996) 62–75. Zbl1100.68031
- L. Trevisan, Parallel approximation algorithms by positive linear programming. Algorithmica21 (1998) 72–88. Zbl0896.68072
- 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.68156

## NotesEmbed ?

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