Quadratic programming and combinatorial minimum weight product problems

Walter  Kern; Gerhard Woeginger

doi:10.1007/11758471_7

Quadratic programming and combinatorial minimum weight product problems

Walter Kern, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
Editors	Tiziana Calamoneri, Irene Finocchi, Giuseppe F. Italiano
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	42-49
ISBN (Electronic)	978-3-540-34378-3
ISBN (Print)	978-3-540-34375-2
DOIs	https://doi.org/10.1007/11758471_7
Publication status	Published - 2006
Event	6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Italy Duration: 29 May 2006 → 31 May 2006 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3998
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Italian Conference on Algorithms and Complexity, CIAC 2006
Abbreviated title	CIAC
Country	Italy
City	Rome
Period	29/05/06 → 31/05/06

Keywords

IR-85190

Access to Document

10.1007/11758471_7

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

Cite this

Kern, W., & Woeginger, G. (2006). Quadratic programming and combinatorial minimum weight product problems. In T. Calamoneri, I. Finocchi, & G. F. Italiano (Eds.), Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings (pp. 42-49). (Lecture Notes in Computer Science; Vol. 3998). Springer. https://doi.org/10.1007/11758471_7

@inproceedings{040019975f7f438aad584ac04f13e869,

title = "Quadratic programming and combinatorial minimum weight product problems",

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.",

keywords = "IR-85190",

author = "Walter Kern and Gerhard Woeginger",

year = "2006",

doi = "10.1007/11758471_7",

language = "English",

isbn = "978-3-540-34375-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "42--49",

editor = "Tiziana Calamoneri and Irene Finocchi and Italiano, {Giuseppe F.}",

booktitle = "Algorithms and Complexity",

note = "6th Italian Conference on Algorithms and Complexity, CIAC 2006, CIAC ; Conference date: 29-05-2006 Through 31-05-2006",

}

Kern, W & Woeginger, G 2006, Quadratic programming and combinatorial minimum weight product problems. in T Calamoneri, I Finocchi & GF Italiano (eds), Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. Lecture Notes in Computer Science, vol. 3998, Springer, Berlin, Heidelberg, pp. 42-49, 6th Italian Conference on Algorithms and Complexity, CIAC 2006, Rome, Italy, 29/05/06. https://doi.org/10.1007/11758471_7

Quadratic programming and combinatorial minimum weight product problems. / Kern, Walter ; Woeginger, Gerhard.

Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. ed. / Tiziana Calamoneri; Irene Finocchi; Giuseppe F. Italiano. Berlin, Heidelberg : Springer, 2006. p. 42-49 (Lecture Notes in Computer Science; Vol. 3998).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Quadratic programming and combinatorial minimum weight product problems

AU - Kern, Walter

AU - Woeginger, Gerhard

N1 - Conference code: 6

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - IR-85190

U2 - 10.1007/11758471_7

DO - 10.1007/11758471_7

M3 - Conference contribution

SN - 978-3-540-34375-2

T3 - Lecture Notes in Computer Science

SP - 42

EP - 49

BT - Algorithms and Complexity

A2 - Calamoneri, Tiziana

A2 - Finocchi, Irene

A2 - Italiano, Giuseppe F.

PB - Springer

CY - Berlin, Heidelberg

T2 - 6th Italian Conference on Algorithms and Complexity, CIAC 2006

Y2 - 29 May 2006 through 31 May 2006

ER -