@article{6efe90b2b0b041cab1e473c111914d3d,
title = "On Clustering Bodies: Geometry and Polyhedral Approximation",
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.",
keywords = "Computational convexity, Convex maximization, Geometric clustering, Optimization, Permutahedron, Polynomial approximation",
author = "Andreas Brieden and Peter Gritzmann",
note = "Funding Information: Received 18 March 1996; sent for revision 1 May 1996; accepted 29 September 1997. Supported by Centre de recherche en toxicologie de l{\textquoteright}environnement(T XEON), Uievrsint{\'e} du Qu{\'e}bec {\`a} Montr{\'e}al, and by the Canadian Network of Toxicology Centres (CNTC). Address correspondence toDnis Felpio,D{\'e} partement des Sciences Biologiques, Universit{\'e} du Qu{\'e}bec {\`a} Montr{\'e}al, C.P. 8888, Succursale Centre-Ville, Montr{\'e}al, Qu{\'e}bec, Canada, H3C 3P8.",
year = "2010",
doi = "10.1007/s00454-009-9226-7",
language = "English",
volume = "44",
pages = "508--534",
journal = "Discrete and Computational Geometry",
issn = "0179-5376",
publisher = "Springer New York",
number = "3",
}