  


An FPTAS for Minimizing the Product of Two Nonnegative Linear Cost Functions
Vineet Goyal (vgoyalandrew.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 submodular 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$mincuts. 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 nonnegative cost functions. Keywords: Quadratic Programming, Approximation Schemes, Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Nonlinear Optimization (Quadratic Programming ) Citation: GSIA Working Paper #2008E16, Tepper School of Business, April 2008 Download: [PDF] Entry Submitted: 06/06/2008 Modify/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  