Quadratic Programming and Combinatorial Minimum Weight Product Problems

摘要

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a~Tx + γ)(b~Tx + δ) under linear constraints Ax ≤ d. Examples of such problems are combinatorial minimum weight product problems such as, e.g., the following: Given a graph G = (V, E) and two edge weights a, b : E → R_+ find an s — t path P that minimizes a(P)b(P), the product of its edge weights relative to a and b.