Title
Maximum dispersion and geometric maximum weight cliques
Authors
-
Publication
Extended abstract in: APPROX '2000, Springer LNCS #1913, 132-143, full version submitted for publication.
Source
-
Classification
-
| MSC: |
| primary: | 90C27 | Combinatorial optimization |
| secondary: | 90B80 | Discrete location and assignment |
Keywords
-
clique, point dispersion, subgraph problem,
geometric optimization,
approximation, rectilinear norm
-
-
We consider geometric instances of
the problem of finding a maximum weight
k-clique of a graph with nonnegative edge
weights. In particular, we present algorithmic
results for the case where vertices are
represented by points in d-dimensional space,
and edge weights correspond to rectilinear
distances. This problem has been considered
before, with the best result being an
approximation algorithm with performance ratio
2. For the case where k is fixed, we establish a
linear-time algorithm that finds an optimal
solution. For the case where k is part of
the input, we present a polynomial-time
approximation scheme.
