Quadratic programming and combinatorial minimum weight product problems

Kern, Walter and Woeginger, Gerhard (2007) Quadratic programming and combinatorial minimum weight product problems. Mathematical programming, 110 (3). pp. 641-649. ISSN 0025-5610

PDF
Restricted to UT campus only: Request a copy
166Kb

Abstract:	We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective $(a^Tx + \gamma)(b^Tx + \partial)$ under linear constraints $Ax \le 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\to\mathbb{R}_+$ find an $s$ - $t$ path $P$ that minimizes $a(P)b(P),$ the product of its edge weights relative to $a$ and $b$ .
Item Type:	Article
Copyright:	© 2007 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/61921
Official URL:	http://dx.doi.org/10.1007/s10107-006-0047-7
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241915