On Clustering Bodies: Geometry and Polyhedral Approximation
On Clustering Bodies: Geometry and Polyhedral Approximation
复制标题
关于聚类体：几何和多面体近似
DOI：
--
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
P. Gritzmann
中科院分区：
文献类型：
--
作者：
A. Brieden;P. Gritzmann
本文研究有限维实空间中某些类别的闭凸集，其动机是它们在凸最大化问题中的应用，尤其是那些从几何聚类演变而来的问题。虽然这些优化问题通常很难，但只要相关聚类体的适当多面体近似可用，就可以设计多项式时间近似算法。在这里，我们给出了导致紧密近似的各种结构结果。
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.