Name
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, whose defining polyhedra contain the clusters, respectively. Further, we characterize strongly feasible centroidal power diagrams in terms of the local optima of some ellipsoidal function over the gravity polytope. The global optima can also be characterized in terms of the separation properties of the corresponding clusterings. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/110832707 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
clustering,weighted clustering,constrained clustering,power diagram,gravity body,gravity polytope | Extreme point,Power diagram,Discrete mathematics,Approximation algorithm,Combinatorics,Local optimum,Polyhedron,Minkowski space,Polytope,Constrained clustering,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 2 | 0895-4801 |
Citations | PageRank | References |
9 | 0.65 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Brieden | 1 | 43 | 5.11 |
| Peter Gritzmann | 2 | 412 | 46.93 |