New algorithms for k-center and extensions |
| |
Authors: | René Brandenberg Lucia Roth |
| |
Institution: | (1) Multidisciplinary Aerospace Design Optimization Research Center, College of Aerospace and Material Engineering, National University of Defense Technology, 410073 Changsha, China |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|