Quadratic programming and combinatorial minimum weight product problems

Share/Save/Bookmark

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

[img]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:
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

 

Repository Staff Only: item control page

Metis ID: 241915