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

László Lovász, Santosh Vempala

Type: Article

Publication Date: 2005-11-10

Citations: 267

DOI: https://doi.org/10.1016/j.jcss.2005.08.004

View Publication

Locations

Journal of Computer and System Sciences - View

Similar Works

Action	Title	Year	Authors
+	Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm	2004	L. Lovasz S. Vempala
+	Quantum algorithm for estimating volumes of convex bodies	2019	Shouvanik Chakrabarti Andrew M. Childs Shih-Han Hung Tongyang Li Chunhao Wang Xiaodi Wu
+ PDF Chat	Quantum Algorithm for Estimating Volumes of Convex Bodies	2023	Shouvanik Chakrabarti Andrew M. Childs Shih-Han Hung Tongyang Li Chunhao Wang Xiaodi Wu
+ PDF Chat	Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies	2020	Apostolos Chalkis Ioannis Z. Emiris Vissarion Fisikopoulos
+	Practical Volume Estimation by a New Annealing Schedule for Cooling Convex Bodies.	2019	Apostolos Chalkis Ioannis Z. Emiris Vissarion Fisikopoulos
+	A practical algorithm for volume estimation based on billiard trajectories and simulated annealing	2019	Apostolos Chalkis Ioannis Z. Emiris Vissarion Fisikopoulos
+ PDF Chat	A Practical Algorithm for Volume Estimation based on Billiard Trajectories and Simulated Annealing	2023	Apostolos Chalkis Ioannis Z. Emiris Vissarion Fisikopoulos
+	Volume of a convex body	2003	Mark Jerrum
+	Random walks in a convex body and an improved volume algorithm	1993	László Lovász Miklós Simonovits
+	Optimization Algorithms for Computational Geometry	2014	Zeyuan Allen-Zhu Zhenyu Liao Lorenzo Orecchia Yang Yuan
+	Volumes in High Dimension	2002	Jiřı́ Matoušek
+	A random polynomial time algorithm for approximating the volume of convex bodies	1989	Martin Dyer Alan Frieze
+	Overlap of Convex Polytopes under Rigid Motion	2012	Hee-Kap Ahn Siu-Wing Cheng Hyuk Jun Kweon Juyoung Yon
+	Simulated Annealing for Convex Optimization	2006	Adam Tauman Kalai Santosh Vempala
+	Random Approximation of Convex Bodies: Monotonicity of the Volumes of Random Tetrahedra	2017	Stefan Kunis Benjamin Reichenwallner Matthias Reitzner
+	Sampling convex bodies: a random matrix approach	2006	Guillaume Aubrun
+	Bypassing KLS: Gaussian Cooling and an O*(n^3) Volume Algorithm	2014	Ben Cousins Santosh Vempala
+	Reducing Isotropy and Volume to KLS: An $O(n^3ψ^2)$ Volume Algorithm	2020	Jia He Aditi Laddha Yin Tat Lee Santosh Vempala
+	Computing the volume of convex bodies: a case where randomness provably helps	1991	Martin Dyer Alan Frieze
+	Estimating the volume of a convex body	2018	Nicolai Baldin

Works That Cite This (204)

Action	Title	Year	Authors
+	A practical volume algorithm	2015	Ben Cousins Santosh Vempala
+ PDF Chat	Error bounds for Metropolis–Hastings algorithms applied to perturbations of Gaussian measures in high dimensions	2014	Andreas Eberle
+ PDF Chat	Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting	2007	Daniel Štefankovič Santosh Vempala Eric Vigoda
+	Annealing and tempering for sampling and counting	2007	Dana Randall Eric Vigoda Nayantara Bhatnagar
+ PDF Chat	Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies	2020	Apostolos Chalkis Ioannis Z. Emiris Vissarion Fisikopoulos
+ PDF Chat	Simulating sticky particles: A Monte Carlo method to sample a stratification	2020	Miranda Holmes‐Cerfon
+	An FPTAS for the volume of some <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.svg"><mml:mi mathvariant="script">V</mml:mi></mml:math>-polytopes — It is hard to compute the volume of the intersection of two cross-polytopes	2020	Ei Ando Shuji Kijima
+	Online Newton Step Algorithm with Estimated Gradient	2018	Binbin Liu Jundong Li Yunquan Song Xijun Liang Ling Jian Huan Liu
+ PDF Chat	Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk	2019	Oren Mangoubi Nisheeth K. Vishnoi
+ PDF Chat	Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases	2020	Nima Anari Michał Dereziński

Works Cited by This (20)

Action	Title	Year	Authors
+	Where to Start a Geometric Random Walk	2003	László Lovász Santosh Vempala
+	Computing the volume of convex bodies: a case where randomness provably helps	1991	Martin Dyer Alan Frieze
+	The Geometry of Logconcave Functions and an O* (n3) Sampling Algorithm	2003	László Lovász Santosh Vempala
+	The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume	2002	László Lovász Miklós Simonovits
+	Random Vectors in the Isotropic Position	1999	Mark Rudelson
+ PDF Chat	A geometric inequality and the complexity of computing volume	1986	Gy. Elekes
+	Hit-and-run from a corner	2004	László Lovász Santosh Vempala
+	On a Certain Converse of Hölder’s Inequality	1972	Л. Леиндлер
+	�ber eine Klasse superadditiver Mengenfunktionale von Brunn-Minkowski-Lusternikschem Typus	1957	Alexander Dinghas
+	Random walks and anO*(n5) volume algorithm for convex bodies	1997	Ravi Kannan L�szl� Lov�sz Mikl�s Simonovits