Fekete, Sándor P.Meijer, Henk2021-12-172021-12-1720002197-8085https://depositonce.tu-berlin.de/handle/11303/15964http://dx.doi.org/10.14279/depositonce-14737We 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.en510 Mathematikcliquepoint dispersionsubgraph problemgeometric optimizationapproximationrectilinear normResearch Paper