Benutzer: Gast  Login
Dokumenttyp:
Zeitschriftenaufsatz 
Autor(en):
Brandenberg, R. and L. Roth 
Titel:
New algorithms for k-center and extensions 
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. Recent developments based on so-...    »
 
Stichworte:
Approximation algorithms, Branch-and-bound, Computational geometry, Geometric inequalities, Containment, Core-sets, k-center, Diameter partition, SOCP, 2-SAT 
Zeitschriftentitel:
Journal of Combinatorial Optimization 
Jahr:
2009 
Heft / Issue:
18 
Seitenangaben Beitrag:
376-392 
Reviewed:
ja 
Sprache:
en 
Publikationsdatum:
21.05.2009 
TUM Einrichtung:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik