User: Guest  Login
Title:

On optimal weighted balanced clusterings: gravity bodies and power diagrams

Document type:
Zeitschriftenaufsatz
Author(s):
Brieden, A. and P. Gritzmann
Abstract:
We study weighted clustering problems in Minkowski spaces under balancing constraints with a view towards separation properties. First, we introduce the gravity polytopes and more general gravity bodies that encode all feasible clusterings and indicate how they can be utilized to develop efficient approximation algorithms for quite general, hard to compute objective functions. Then we show that their extreme points correspond to strongly feasible power diagrams, certain specific cell complexes,...     »
Journal title:
SIAM Journal on Discrete Mathematics
Year:
2012
Journal issue:
26
Pages contribution:
415-434
Reviewed:
ja
Language:
en
TUM Institution:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
 BibTeX