Quadratic programming and combinatorial minimum weight product problems

Walter Kern, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)

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 languageEnglish
Pages (from-to)641-649
Number of pages9
JournalMathematical programming
Volume110
Issue number3
DOIs
Publication statusPublished - Sep 2007

Keywords

  • MSC-90C27
  • MSC-90C26
  • MSC-90C20
  • Shortest path
  • Quadratic programming
  • Approximation scheme

Fingerprint

Dive into the research topics of 'Quadratic programming and combinatorial minimum weight product problems'. Together they form a unique fingerprint.

Cite this