Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
verfasst von : Benjamin E. Birnbaum, Kenneth J. Goldman
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
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
Given a positive integer
p
and a complete graph with non-negative edge weights that satisfy the triangle inequality, the
remote-clique
problem is to find a subset of
p
vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this paper, we present an algorithm called
d
-
Greedy Augment
that generalizes this greedy algorithm (they are equivalent when
d
= 1). We use the technique of
factor-revealing linear programs
to prove that
d
-
Greedy Augment
, which has a running time of
O
(
pdn
d
), achieves an approximation ratio of (2
p
– 2)/(
p
+
d
– 2). Thus, when
d
= 1,
d
-
Greedy Augment
achieves an approximation ratio of 2 and runs in time
O
(
pn
), making it the fastest known 2-approximation for the remote-clique problem. The usefulness of factor-revealing LPs in the analysis of
d
-
Greedy Augment
suggests possible applicability of this technique to the study of other approximation algorithms.