Abstract
We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a T x + ¿)(b T x + d) under linear constraints A x = d. Examples of such problems are combinatorial minimum weight product problems such as the following: given a graph G = (V,E) and two edge weights find an s - t path P that minimizes a(P)b(P), the product of its edge weights relative to a and b.
| Original language | English |
|---|---|
| Pages (from-to) | 641-649 |
| Journal | Mathematical Programming |
| Volume | 110 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2007 |