Optimization Online


An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions

Vineet Goyal (vgoyal***at***andrew.cmu.edu)
Latife Genc-Kaya (lgenc***at***andrew.cmu.edu)
R. Ravi (ravi***at***andrew.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/2008
Entry Accepted: 06/07/2008
Entry Last Modified: 06/11/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society