Geodesic Walks in Polytopes

DOI10.1137/17M1145999MaRDI QIDQ5073522zbMATH OpenOpenAlexFDO

Authors Yin Tat Lee, Santosh S. Vempala

Publication date 3 May 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/17m1145999

zbMATH Keywords

geodesic walkHessian manifoldlog barrierODEsampling polytopesSDE

Mathematics Subject Classification ID

Manifolds of metrics (especially Riemannian) (58D17) Monte Carlo methods (65C05) Randomized algorithms (68W20)

Recommendations

• Geodesic walks in polytopes
• Vertex to Vertex Geodesics on Platonic Solids
• Geodesic geometry on graphs
• Geodesics on regular polyhedra with endpoints at the vertices
• Geodesic Flow on Ideal Polyhedra
• Closed geodesics on regular polyhedra
• Geodesics and steps in a connected graph
• scientific article; zbMATH DE number 1305036

Cites work

• A cubic algorithm for computing Gaussian volume
• A First Course in the Numerical Analysis of Differential Equations
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A visual introduction to Riemannian curvatures and some discrete generalizations
• Canonical barriers on convex cones
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
• Hit-and-Run from a Corner
• Hit-and-run mixes fast
• scientific article; zbMATH DE number 4078444 (Why is no real title available?)
• scientific article; zbMATH DE number 18983 (Why is no real title available?)
• scientific article; zbMATH DE number 65730 (Why is no real title available?)
• scientific article; zbMATH DE number 1256686 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 4197739 (Why is no real title available?)
• scientific article; zbMATH DE number 5019925 (Why is no real title available?)
• Natural algorithms for flow problems
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• Primal central paths and Riemannian distances for convex sets
• Random walks and anO*(n5) volume algorithm for convex bodies
• Random walks in a convex body and an improved volume algorithm
• Random walks on polytopes and an affine interior point method for linear programming
• Randomized interior point methods for sampling and optimization
• Rapid mixing of geodesic walks on manifolds with positive curvature
• Riemannian geometry and geometric analysis
• Sampling from a log-concave distribution with projected Langevin Monte Carlo
• THE CURVATURE OF A HESSIAN METRIC
• The entropic barrier: exponential families, log-concave geometry, and self-concordance

Cited in

(4)

• 3D positive lattice walks and spherical triangles
• Wandering polygons and recurrent critical leaves
• Novel matrix hit and run for sampling polytopes and its GPU implementation
• Efficient random walks on Riemannian manifolds

This page was built for publication: Geodesic Walks in Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5073522)