Simulated annealing in convex bodies and an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msup><mml:mrow><mml:mi>O</mml:mi></mml:mrow><mml:mrow><mml:mo>*</mml:mo></mml:mrow></mml:msup><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mrow><mml:mn>4</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> volume algorithm
Journal of Computer and System SciencesPublished 10 November 2005
László Lovász, Santosh Vempala
Citations250
SJR quartileQ1
SJR score1.03
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new algorithm for computing the volume of a convex body in R^n is presented, improving on the previous best algorithm by a factor of n and using a ''morphing'' technique that can be viewed as a variant of simulated annealing.
Abstract
We present a new algorithm for computing the volume of a convex body in Rn. The main ingredients of the algorithm are (i) a "morphing" technique that can be viewed as a variant of simulated annealing and (ii) a new rounding algorithm to put a convex body in near-isotropic position. The complexity is O*(n4), improving on the previous best algorithm by a factor of n.
Keywords
Computer ScienceMathematics
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Algorithms and combinatoricsGeometric Algorithms and Combinatorial Optimization
3,487 Citations1988Martin Grötschel, László Lovász +1 more
This paper presents a meta-modelling framework for estimating the running time of Oracle Algorithms, and some examples show how this framework can be modified for more efficient and scalable solutions to NP-Completeness problems.
Theoretical Computer ScienceRandom generation of combinatorial structures from a uniform distribution
1,003 Citations1986Mark Jerrum, Leslie G. Valiant +1 more
It is shown that exactly uniform generation of ‘efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy).
Journal of the ACMA random polynomial-time algorithm for approximating the volume of convex bodies
701 Citations1991Martin Dyer, Alan Frieze +1 more
The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K within Euclidean space.
Random Structures and AlgorithmsRandom walks in a convex body and an improved volume algorithm
425 Citations1993László Lovász, Miklós Simonovits
A randomized algorithm using O(n7 log’ n) separation calls to approximate the volume of a convex body with a fixed relative error is given and the mixing rate of Markov chains from finite to arbitrary Markov Chains is analyzed.
Discrete & Computational GeometryIsoperimetric problems for convex bodies and a localization lemma
403 Citations1995Ravi Kannan, László Lovász +1 more
This lemma is a general “Localization Lemma” that reduces integral inequalities over then-dimensional space to integral inequalities in a single variable and is illustrated by showing how a number of well-known results can be proved using it.
Journal of Functional AnalysisRandom Vectors in the Isotropic Position
398 Citations1999Mark Rudelson
Random Structures and AlgorithmsRandom walks and anO*(n5) volume algorithm for convex bodies
293 Citations1997Ravi Kannan, L�szl� Lov�sz +1 more
This algorithm introduces three new ideas: the use of the isotropic position (or at least an approximation of it) for rounding; the separation of global obstructions and local obstructions for fast mixing; and a stepwise interlacing of rounding and sampling.
Journal of the ACMSolving convex programs by random walks
253 Citations2004Dimitris Bertsimas, Santosh Vempala
A simple new algorithm for convex optimization based on sampling by a random walk is presented, which extends naturally to minimizing quasi-convex functions and to other generalizations.
The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume
198 Citations2002László Lovász, Miklós Simonovits
The authors generalize a bound on the mixing rate of time-reversible Markov chains in terms of their conductance by not assuming time reversibility and using a weaker notion of conductance and prove an isoperimetric inequality for subsets of a convex body.
Sampling and integration of near log-concave functions
144 Citations1991David Applegate, Ravi Kannan
This work provides the first polynomial time algorithm to generate samples from a given log-concave distribution and proves a general isoperimetric inequality for convex sets and uses this together with recent developments in the theory of rapidly mixing Markov chains.
Proceedings of symposia in applied mathematicsComputing the volume of convex bodies: a case where randomness provably helps
123 Citations1991Martin Dyer, Alan Frieze
The problem of computing the volume of a convex body K in R is discussed and worst-case results are reviewed and randomised approximation algorithms which show that with randomisation one can approximate very nicely are provided.
Discrete & Computational GeometryComputing the volume is difficult
122 Citations1987Imre Bárány, Zoltán Füredi
Discrete & Computational GeometryA geometric inequality and the complexity of computing volume
117 Citations1986Gy. Elekes
The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2n, which implies that no polynomial time algorithm can compute the volume of a convex set given by an oracle with less than exponential relative error.
Hit-and-run from a corner
53 Citations2004László Lovász, Santosh Vempala
It is shown that the hit-and-run random walk mixes rapidly starting from any interior point of a convex body, the first random walk known to have this property.
Hit-and-Run is Fast and Fun 1
52 Citations2003Santosh Vempala
A natural extension of the hit-and-run algorithm to sampling from a logconcave distribution in n dimensions produces a point from approximately the right distribution in amortized time O ∗ ( n 3 ).
On the randomized complexity of volume and diameter
48 Citations1992László Lovász, Miklós Simonovits
The authors give an O(n/sup 7/log/sup 2/n) randomised algorithm to approximate the volume of a convex body, and an O (n/Sup 6/log n) algorithm to sample a point from the uniform distribution over a conveX body.
Random Points in Isotropic Convex Sets
43 Citations1999Jean Bourgain
Logconcave functions: geometry and efficient sampling algorithms
23 Citations2004László Lovász, Santosh Vempala
The geometry of logconcave functions in R/sup n/ is studied and an analysis technique for "smoothing" them out is introduced, leading to efficient sampling algorithms with no assumptions on the local smoothness of the density function.
The Geometry of Logconcave Functions and an O* (n3) Sampling Algorithm
21 Citations2003László Lovász, Santosh Vempala
This work studies the geometry of logconcave functions in R n and introduces a technique for “smoothing” them out, which leads to an efficient sampling algorithm with no assumptions on the local smoothness of the density function.
Where to Start a Geometric Random Walk
7 Citations2003László Lovász, Santosh Vempala