Quadratic programming and combinatorial minimum weight product problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (aT x + ¿)(bTx + d) 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 (Proceedings 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006)
EditorsT. Calamoneri, I. Finocchi, G.F. Italiano
Place of PublicationBerlin
PublisherSpringer
Pages42-49
ISBN (Print)3-540-34375-X
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume3998
ISSN (Print)0302-9743

Fingerprint

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

Cite this