Abstract
The present paper studies certain classes of closed convex sets in finite-dimensional real spaces that are motivated by their application to convex maximization problems, most notably, those evolving from geometric clustering. While these optimization problems are ℕℙ-hard in general, polynomial-time approximation algorithms can be devised whenever appropriate polyhedral approximations of their related clustering bodies are available. Here we give various structural results that lead to tight approximations.
Original language | English |
---|---|
Pages (from-to) | 508-534 |
Number of pages | 27 |
Journal | Discrete and Computational Geometry |
Volume | 44 |
Issue number | 3 |
DOIs | |
State | Published - 2010 |
Keywords
- Computational convexity
- Convex maximization
- Geometric clustering
- Optimization
- Permutahedron
- Polynomial approximation