Paper Info
Title
Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming
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.
Year
DOI
Venue
2008
10.1051/ita:2007032
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Keywords
Field
DocType
parallel approximation,quadratic programming,multiplicity scheduling problem
Discrete mathematics,Combinatorics,Polynomial,Algebra,Scheduling (computing),Multiplicity (mathematics),Quadratic equation,Quadratic programming,Time complexity,Mathematics
Journal
Volume
Issue
ISSN
42
2
0988-3754
Citations 
PageRank 
References 
0
0.34
18
Authors
2
Name
Order
Citations
PageRank
Maria J. Serna147370.53
Fatos Xhafa23433343.33