Thumbnail Image

Maximum dispersion and geometric maximum weight cliques

Fekete, Sándor P.; Meijer, Henk

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.