On the parallel approximability of a subclass of quadratic programming

In this paper we deal with the parallel approximability of a special class of quadratic programming (QP), called smooth quadratic programming. This su bclass of QP is obtained by imposing restrictions on the coefficients of QP instance, namely the smoothness and positiveness restrictions. The smoothn ess condition restricts the magnitudes of the coefficients of the instance while the positiveness condition requires that (part of) the coefficients o f the instance be nonnegative. 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 s cheme (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 approximat ion procedure is obtained by reducing the instance of QP to an instance of positive linear programming, finding in NC an approximate fractional soluti on 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 p roblems. (C) 2001 Elsevier Science B.V. All rights reserved.