New algorithms for k-center and extensions

René Brandenberg () and Lucia Roth ()
Additional contact information
René Brandenberg: Technische Universität München
Lucia Roth: Technische Universität München

Journal of Combinatorial Optimization, 2009, vol. 18, issue 4, No 5, 376-392

Abstract: Abstract The problem of interest is covering a given point set with homothetic copies of several convex containers C 1,…,C k , 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 C i are Euclidean unit balls. Recent developments based on so-called core-sets enable not only better theoretical bounds in the running time of approximation algorithms but also improvements in practically solvable input sizes. Here, we present some new geometric inequalities and a Mixed-Integer-Convex-Programming formulation. Both are used in a very effective branch-and-bound routine which not only improves on best known running times in the Euclidean case but also handles general and even different containers among the C i .

Keywords: Approximation algorithms; Branch-and-bound; Computational geometry; Geometric inequalities; Containment; Core-sets; k-center; Diameter partition; SOCP; 2-SAT (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9226-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:18:y:2009:i:4:d:10.1007_s10878-009-9226-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9226-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().