On Clustering Bodies: Geometry and Polyhedral Approximation

Andreas Brieden, Peter Gritzmann

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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 languageEnglish
Pages (from-to)508-534
Number of pages27
JournalDiscrete and Computational Geometry
Volume44
Issue number3
DOIs
StatePublished - 2010

Keywords

  • Computational convexity
  • Convex maximization
  • Geometric clustering
  • Optimization
  • Permutahedron
  • Polynomial approximation

Fingerprint

Dive into the research topics of 'On Clustering Bodies: Geometry and Polyhedral Approximation'. Together they form a unique fingerprint.

Cite this