On the parallel approximability of a subclass of quadratic programming. (Q5941277)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the parallel approximability of a subclass of quadratic programming. |
scientific article; zbMATH DE number 1635442
Language | Label | Description | Also known as |
---|---|---|---|
English | On the parallel approximability of a subclass of quadratic programming. |
scientific article; zbMATH DE number 1635442 |
Statements
On the parallel approximability of a subclass of quadratic programming. (English)
0 references
20 August 2001
0 references
In this paper we deal with the parallel approximability of a special class of quadratic programming (QP), called smooth quadratic programming. This subclass of QP is obtained by imposing restrictions on the coefficients of QP instance, namely the smoothness and positiveness restrictions. The smoothness condition restricts the magnitudes of the coefficients of the instance while the positiveness condition requires that (part of) the coefficients of the instance be non-negative. Interestingly, even with these restrictions several combinatorial optimization problems are captured by this class. We show that there is a parallel additive approximation procedure to instances of smooth QP. The additive procedure translates into an NC approximation scheme (NCAS) when the optimal value of the instance is \(\Omega(n^2)\), where \(n\) is the number of variables of the instance. In particular, the procedure yields an NCAS for positive instances of smooth QP. The additive approximation procedure is obtained by reducing the instance of QP to an instance of positive linear programming, finding in NC an approximate fractional solution to the obtained program, and then rounding the fractional solution to an integer approximate solution for the original problem. Next, we extend the result to instances of bounded degree Smooth Integer Programming. Finally, we consider several combinatorial problems that are modeled by smooth QP (or smooth integer programs) and show that the techniques presented here can be used to obtain NC Approximation Schemes for ``dense'' instances of such problems.
0 references
Parallel approximations
0 references
Quadratic programming
0 references
Packing / covering linear programs
0 references
Randomized rounding
0 references
Dense instances
0 references
0 references