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 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.
- Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
- Approximating quadratic programming with bound and quadratic constraints
- Approximation algorithms for quadratic programming
- Parallel approximation algorithms by positive linear programming
- Positive linear programming, parallel approximation and PCP's
- A parallel approximation algorithm for positive linear programming
- Approximating linear programming is log-space complete for P
- Computationally Related Problems
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- scientific article; zbMATH DE number 3637614 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- scientific article; zbMATH DE number 1163722 (Why is no real title available?)
- scientific article; zbMATH DE number 784042 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Improved parallel approximation of a class of integer programming problems
- Linear programming is log-space hard for P
- Paradigms for Fast Parallel Approximability
- Parallel approximation algorithms by positive linear programming
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Quadratic programming is in NP
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Randomness is linear in space
- The ellipsoid method and its consequences in combinatorial optimization
- The probabilistic method yields deterministic parallel algorithms
This page was built for publication: On the parallel approximability of a subclass of quadratic programming.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941277)
