Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

Simple item page
dc.creatorChandrasekaran, Karthekeyan
dc.creatorDadush, Daniel
dc.creatorVempala, Santosh
dc.date2009-04-03
dc.date.accessioned2026-07-07T13:00:18Z
dc.date.available2026-07-07T13:00:18Z
dc.descriptionStar-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an efficient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard.
dc.identifierhttps://arxiv.org/abs/0904.0583
dc.identifierhttp://arxiv.org/abs/0904.0583
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/225808
dc.subjectData Structures and Algorithms
dc.subjectFunctional Analysis
dc.subjectProbability
dc.subjectF.2.2
dc.titleThin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
dc.typetext

Files

Collections

arXiv