An FPTAS for minimizing the product of two non-negative linear cost functions
成果类型：
Article
署名作者：
Goyal, Vineet; Genc-Kaya, Latife; Ravi, R.
署名单位：
Carnegie Mellon University; Massachusetts Institute of Technology (MIT)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-009-0287-4
发表日期：
2011
页码：
401-405
关键词：
摘要：
We consider a quadratic programming (QP) problem (Pi) of the form min x(T) Cx subject to Ax >= b, x >= 0 where C is an element of R-+(nxn), rank(C) = 1 and A is an element of R-mxn, b is an element of R-m. We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Pi) 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 Pi models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.