User: Guest  Login
Title:

On clustering bodies: Geometry and polyhedra approximation

Document type:
Zeitschriftenaufsatz
Author(s):
Brieden, A. and P. Gritzmann
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 app...     »
Keywords:
Computational convexity, Optimization, Geometric clustering, Convex maximization, Polynomial approximation, Permutahedron
Journal title:
Discrete & Computational Geometry
Year:
2010
Journal issue:
44
Pages contribution:
508-534
Reviewed:
ja
Language:
en
TUM Institution:
Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
 BibTeX