Benutzer: Gast  Login
Titel:

New Algorithms for k-Center and Extensions

Dokumenttyp:
Konferenzbeitrag
Art des Konferenzbeitrags:
Textbeitrag / Aufsatz
Autor(en):
Brandenberg, René; Roth, Lucia
Seitenangaben Beitrag:
64-78
Abstract:
The problem of interest is covering a given point set with homothetic copies of several convex containers C1, ..., Ck, while the objective is to minimize the maximum over the dilatation factors. Such k-containment problems arise in various applications, e.g. in facility location, shape fitting, data classification or clustering. So far most attention has been paid to the special case of the Euclidean k-center problem, where all containers Ci are Euclidean unit balls. New developments based on so...     »
Stichworte:
approximation algorithms, branch-and-bound, computational geometry, geometric inequalities, containment, core-sets, k-center diameter,, partition, SOCP, 2-SAT
Kongress- / Buchtitel:
Lecture Notes in Computer Science 5165
Jahr:
2008
Reviewed:
ja
Sprache:
en
TUM Einrichtung:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
 BibTeX