Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Quadratic Programming and Combinatorial Minimum Weight Product Problems
verfasst von : Walter Kern, Gerhard Woeginger
Erschienen in: Algorithms and Complexity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a fully polynomial time approximation scheme (FPTAS) for minimizing an objective (
a
T
x
+
γ
)(
b
T
x
+
δ
) 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
${\bf a, b}: E \to {\mathbb R}_{+}$
find an
s
–
t
path
P
that minimizes
a
(
P
)
b
(
P
), the product of its edge weights relative to
a
and
b
.
AMS-Class:
90C20, 90C26, 90C27.