We consider a quadratic programming (QP) problem ($\Pi$) of the form $\min x^T C x$ subject to $Ax \ge b$ where $C\in {\mathbb R}^{n\mbox{\tiny\texttimes} n}_+, rank(C)=1$ and $A\in {\mathbb R}^{m\mbox{\tiny\texttimes} n}, b\in {\mathbb R}^m$. We present an FPTAS for this problem by reformulating the QP ($\Pi$) as a parametrized LP and ``rounding'' the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to $0$-$1$ problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. We also extend our results to problems for which the convex hull of the dominant of the feasible integer solutions is known such as $s,t$-shortest paths and $s,t$-min-cuts. For the above discrete problems, the quadratic program $\Pi$ models the problem of obtaining an integer solution that minimizes the {\em product} of two linear non-negative cost functions.
Citation
GSIA Working Paper #2008-E16, Tepper School of Business, April 2008
Article
View An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions