An FPTAS for Minimizing the Product of Two Non-negative Linear Co.pdf.pdf' (155.84 kB)

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

journal contribution

posted on 01.09.2006, 00:00 authored by Vineet Goyal, Latife Genç-Kaya, Ramamoorthi RaviRamamoorthi RaviWe consider a quadratic programming (QP) problem (∏) of the form min x

^{T}Cx subject to Ax ≥ b where C ∈ R^{n×n}, rank(C) = 1 and A∈ R^{m×n}; b ∈ R^{m}. We present an FPTAS for this problem by reformulating the QP (∏) as a parameterized 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. They also apply 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 ∏ models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.