Maximum dispersion and geometric maximum weight cliques
| dc.contributor.author | Fekete, Sándor P. | |
| dc.contributor.author | Meijer, Henk | |
| dc.date.accessioned | 2021-12-17T10:18:03Z | |
| dc.date.available | 2021-12-17T10:18:03Z | |
| dc.date.issued | 2000 | |
| dc.description.abstract | 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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15964 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14737 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | clique | en |
| dc.subject.other | point dispersion | en |
| dc.subject.other | subgraph problem | en |
| dc.subject.other | geometric optimization | en |
| dc.subject.other | approximation | en |
| dc.subject.other | rectilinear norm | en |
| dc.title | Maximum dispersion and geometric maximum weight cliques | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2000, 667 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
| tub.subject.msc2000 | 90B80 Discrete location and assignment | en |