Abstract
We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (a T x + γ)(b T x + δ) 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 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.
Original language | English |
---|---|
Article number | 10.1007/s10107-006-0047-7 |
Pages (from-to) | 641-649 |
Number of pages | 9 |
Journal | Mathematical programming |
Volume | 110 |
Issue number | 3 |
DOIs | |
Publication status | Published - Sep 2007 |
Keywords
- MSC-90C27
- Quadratic programming · Approximation scheme · Shortest path
- IR-61921
- MSC-90C26
- MSC-90C20
- EWI-11082
- METIS-241915