Quadratic programming and combinatorial minimum weight product problems

Walter Kern, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

Abstract

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (aTx+γ)(bTx+δ) under linear constraints Ax ≤d. Examples of such problems are combinatorial minimum weight product problems such as, e.g., 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
Title of host publicationAlgorithms and Complexity
Subtitle of host publication6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
EditorsTiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages42-49
ISBN (Electronic)978-3-540-34378-3
ISBN (Print)978-3-540-34375-2
DOIs
Publication statusPublished - 2006
Event6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy
Duration: 29 May 200631 May 2006
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3998
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th Italian Conference on Algorithms and Complexity, CIAC 2006
Abbreviated titleCIAC
CountryItaly
CityRome
Period29/05/0631/05/06

Keywords

  • IR-85190

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

Cite this