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

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 language	English
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
MSC-90C26
MSC-90C20
Shortest path
Quadratic programming
Approximation scheme

Access to Document

10.1007/s10107-006-0047-7

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, MSC-90C26, MSC-90C20, Shortest path, Quadratic programming, Approximation scheme",

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 - MSC-90C26

KW - MSC-90C20

KW - Shortest path

KW - Quadratic programming

KW - Approximation scheme

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

ER -

Quadratic programming and combinatorial minimum weight product problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this