Simulated annealing in convex bodies and an $O^{*}(n^{4}$) volume algorithm

DOI10.1016/j.jcss.2005.08.004zbMath1090.68112OpenAlexW2147487384WikidataQ59410514 ScholiaQ59410514MaRDI QIDQ2490265

Publication date: 28 April 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.08.004

zbMATH Keywords

Simulated annealing Random walks Convex bodies Logconcave functions Volume computation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items

On the mixing time of coordinate Hit-and-Run, Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies, Approximating the stability region for binary mixed-integer programs, Floating bodies and approximation of convex bodies by polytopes, A practical volume algorithm, A parallel implementation of an $O^\ast(n^4)$ volume algorithm, Entanglement in bipartite quantum systems: Euclidean volume ratios and detectability by Bell inequalities, A Fast and Practical Method to Estimate Volumes of Convex Polytopes, Exploring stochasticity and imprecise knowledge based on linear inequality constraints, Random Instances of Problems in NP – Algorithms and Statistical Physics, Stochastic Billiards for Sampling from the Boundary of a Convex Set, Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives, An empirical evaluation of walk-and-round heuristics for mixed integer linear programs, Computing and estimating the volume of the solution space of SMT(LA) constraints, Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization, Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization, Multiobjective Interacting Particle Algorithm for Global Optimization, Hitting time of quantum walks with perturbation, Deciphering the imprint of topology on nonlinear dynamical network stability, Computational results of an $O^{\ast }(n^{4})$ volume algorithm, Convergence of Gibbs sampling: coordinate hit-and-run mixes fast, Markov chains, Hamiltonian cycles and volumes of convex bodies, Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions, An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, Sampling Hypersurfaces through Diffusion, Improved mixing rates of directed cycles by added connection, Dispersion of mass and the complexity of randomized geometric algorithms, Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics, Extended studies of separability functions and probabilities and the relevance of Dyson indices, Using Histograms to Better Answer Queries to Probabilistic Logic Programs, Efficient approximation schemes for economic lot-sizing in continuous time, Near-optimal deterministic algorithms for volume computation via M-ellipsoids, Improved approximations for the Erlang loss model, Approximating the volume of unions and intersections of high-dimensional geometric objects, Unnamed Item, Mixing time of an unaligned Gibbs sampler on the square, Mass volume curves and anomaly ranking, Calculating the free energy of nearly jammed hard-particle packings using molecular dynamics, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, Large margin vs. large volume in transductive learning, A dynamic programming approach to efficient sampling from Boltzmann distributions, The Computational Complexity of Estimating MCMC Convergence Time, Optimization of a convex program with a polynomial perturbation, Approximate weighted model integration on DNF structures, An FPTAS for the volume of some $\mathcal{V} $-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes, Randomly coloring constant degree graphs, Honey from the Hives: A Theoretical and Computational Exploration of Combinatorial Hives, Unnamed Item, Estimating the volume of solution space for satisfiability modulo linear real arithmetic, Randomized interior point methods for sampling and optimization, Strong dispersion property for the quantum walk on the hypercube

Cites Work

Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm