Maximum dispersion and geometric maximum weight cliques

Sándor P. Fekete and Henk Meijer

Extended abstract in: APPROX '2000, Springer LNCS #1913, 132-143, full version submitted for publication.

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.

Download as [PDF] [ps.gz] [ps]