direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

Maximum dispersion and geometric maximum weight cliques
Zitatschlüssel Report-667-2000
Autor Sándor P. Fekete and Henk Meijer
Jahr 2000
Nummer 667
Notiz Extended abstract in: APPROX '2000, Springer-Verlag LNCS 1913, 132–143, full version submitted for publication.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag