- An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions Vineet Goyal (vgoyalandrew.cmu.edu) Latife Genc-Kaya (lgencandrew.cmu.edu) R. Ravi (raviandrew.cmu.edu) Abstract: 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. Keywords: Quadratic Programming, Approximation Schemes, Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Nonlinear Optimization (Quadratic Programming ) Citation: GSIA Working Paper #2008-E16, Tepper School of Business, April 2008 Download: [PDF]Entry Submitted: 06/06/2008Entry Accepted: 06/07/2008Entry Last Modified: 06/11/2008Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.