Quadratic programming and combinatorial minimum weight product problems

Walter  Kern; Gerhard Woeginger

doi:10.1007/s10107-006-0047-7

Quadratic programming and combinatorial minimum weight product problems

Walter Kern, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

15 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 language	English
Article number	10.1007/s10107-006-0047-7
Pages (from-to)	641-649
Number of pages	9
Journal	Mathematical programming
Volume	110
Issue number	3
DOIs	https://doi.org/10.1007/s10107-006-0047-7
Publication status	Published - Sep 2007

Keywords

MSC-90C27
Quadratic programming · Approximation scheme · Shortest path
IR-61921
MSC-90C26
MSC-90C20
EWI-11082
METIS-241915

Access to Document

10.1007/s10107-006-0047-7

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

Cite this

@article{bff53769d5144d85b4b9cadfe4b906c0,

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

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

keywords = "MSC-90C27, Quadratic programming · Approximation scheme · Shortest path, IR-61921, MSC-90C26, MSC-90C20, EWI-11082, METIS-241915",

author = "Walter Kern and Gerhard Woeginger",

year = "2007",

month = sep,

doi = "10.1007/s10107-006-0047-7",

language = "English",

volume = "110",

pages = "641--649",

journal = "Mathematical programming",

issn = "0025-5610",

publisher = "Springer",

number = "3",

}

TY - JOUR

T1 - Quadratic programming and combinatorial minimum weight product problems

AU - Kern, Walter

AU - Woeginger, Gerhard

PY - 2007/9

Y1 - 2007/9

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

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

KW - MSC-90C27

KW - Quadratic programming · Approximation scheme · Shortest path

KW - IR-61921

KW - MSC-90C26

KW - MSC-90C20

KW - EWI-11082

KW - METIS-241915

U2 - 10.1007/s10107-006-0047-7

DO - 10.1007/s10107-006-0047-7

M3 - Article

VL - 110

SP - 641

EP - 649

JO - Mathematical programming

JF - Mathematical programming

SN - 0025-5610

IS - 3

M1 - 10.1007/s10107-006-0047-7

ER -