A random polynomial-time algorithm for approximating the volume of convex bodies
From MaRDI portal
Publication:4302827
DOI10.1145/102782.102783zbMath0799.68107OpenAlexW2063342497WikidataQ55871716 ScholiaQ55871716MaRDI QIDQ4302827
Martin Dyer, Ravindran Kannan, Alan M. Frieze
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/102782.102783
Sums of independent random variables; random walks (60G50) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)
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, Unnamed Item, Geodesic Walks in Polytopes, On the Complexity of Constrained Determinantal Point Processes, Contextual Search via Intrinsic Volumes, Tropical Monte Carlo quadrature for Feynman integrals, From approximate to exact integer programming, Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets, Convex geometry and its connections to harmonic analysis, functional analysis and probability theory, Speeding up random walk mixing by starting from a uniform vertex, The Langevin Monte Carlo algorithm in the non-smooth log-concave case, Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders, Interactions of computational complexity theory and mathematics, Robust Estimation of the Mean with Bounded Relative Standard Deviation, Unnamed Item, Approximate CVP_p in Time 2^{0.802 n}, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, Using Histograms to Better Answer Queries to Probabilistic Logic Programs, Unbounded Discrepancy of Deterministic Random Walks on Grids, Near-optimal deterministic algorithms for volume computation via M-ellipsoids, Approximating the volume of tropical polytopes is difficult, Decoherence in quantum walks – a review, Unnamed Item, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Unnamed Item, Halving the Bounds for the Markov, Chebyshev, and Chernoff Inequalities Using Smoothing, Approximability of the eight-vertex model, Quantum Chebyshev's Inequality and Applications, DISCRETE TIME QUANTUM WALK ON A LINE WITH TWO PARTICLES, Counting Hypergraph Colorings in the Local Lemma Regime, Unnamed Item, Strong dispersion property for the quantum walk on the hypercube, Randomly coloring simple hypergraphs with fewer colors, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Approximating the volume of convex bodies, Fast perfect sampling from linear extensions, A probabilistic interpretation of set-membership filtering: application to polynomial systems through polytopic bounding, Random sampling: billiard walk algorithm, A practical volume algorithm, Covering convex bodies and the closest vector problem, Oracle lower bounds for stochastic gradient sampling algorithms, A parallel implementation of an \(O^\ast(n^4)\) volume algorithm, Concentration phenomena in high dimensional geometry, Estimating the volume of the solution space of SMT(LIA) constraints by a flat histogram method, Efficient sampling in spectrahedra and volume approximation, Exploring stochasticity and imprecise knowledge based on linear inequality constraints, \(t\)-copula from the viewpoint of tail dependence matrices, One-dimensional three-state quantum walk with single-point phase defects, Sampling from a log-concave distribution with projected Langevin Monte Carlo, A CARTOPT METHOD FOR BOUND-CONSTRAINED GLOBAL OPTIMIZATION, A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem, Some more n‐dimensional geometry†, Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, A unifying geometric solution framework and complexity analysis for variational inequalities, On the complete instability of interval polynomials, Total variation discrepancy of deterministic random walks for ergodic Markov chains, Simulating BPP using a general weak random source, The electrical resistance of a graph captures its commute and cover times, The convex geometry of linear inverse problems, Approximate counting in SMT and value estimation for probabilistic programs, Sampling dynamic networks with application to investigation of HIV epidemic drivers, Randomized scheduling algorithm for queueing networks, Computational results of an \(O^{\ast }(n^{4})\) volume algorithm, Randomly coloring simple hypergraphs, Markov chains, Hamiltonian cycles and volumes of convex bodies, Rank-two update algorithms for the minimum volume enclosing ellipsoid problem, Exploiting sparsity for semi-algebraic set volume computation, Large deviations, moderate deviations, and the KLS conjecture, Mixing time of the adjacent walk on the simplex, 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, Mixing times of lozenge tiling and card shuffling Markov chains, (Deterministic) algorithms that compute the volume of polytopes, Probabilistic Lipschitz analysis of neural networks, A generalization of Löwner-John's ellipsoid theorem, Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts, Counting linear extensions: parameterizations by treewidth, Dispersion of mass and the complexity of randomized geometric algorithms, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, Extended studies of separability functions and probabilities and the relevance of Dyson indices, Computing the volume, counting integral points, and exponential sums, Laplace eigenvalues of graphs---a survey, The mixing time of the Dikin walk in a polytope -- a simple proof, On the random generation of monotone data sets, Aggregate operators in constraint query languages, A polynomial number of random points does not determine the volume of a convex body, Efficiency test of pseudorandom number generators using random walks, Experimental validation of volume-based comparison for double-McCormick relaxations, Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm, Learning mixtures of separated nonspherical Gaussians, Uniform generation in spatial constraint databases and applications, Approximating the volume of unions and intersections of high-dimensional geometric objects, Delayed path coupling and generating random permutations, Characterizing limits and opportunities in speeding up Markov chain mixing, Interdependent defense games with applications to internet security at the level of autonomous systems, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, Generating a random collection of discrete joint probability distributions subject to partial information, High-dimensional nonparametric density estimation via symmetry and shape constraints, The accessibility of convex bodies and derandomization of the hit and run algorithm, Approximation of convex sets by polytopes, The Santalo point of a planar convex set, Stochastic boundary methods of fundamental solutions for solving PDEs, Sampling methods for shortest vectors, closest vectors and successive minima, Approximate CVP\(_p\) in time \(2^{0.802n}\), On Sampling from Multivariate Distributions, What do we know about the Metropolis algorithm?, The Computational Complexity of Duality, Random walks on a finite graph with congestion points, On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls, On the limits of nonapproximability of lattice problems, Uniqueness of Gibbs measures for continuous hardcore models, Random sampling of contingency tables via probabilistic divide-and-conquer, Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials, An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes, Book Review: Inevitable randomness in discrete mathematics, A faster tree-decomposition based algorithm for counting linear extensions, Discrete quantum walks hit exponentially faster, Randomly coloring constant degree graphs, Balanced pairs in partial orders, Faster random generation of linear extensions, Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors, Estimating the volume of solution space for satisfiability modulo linear real arithmetic, Heat flow and a faster algorithm to compute the surface area of a convex body, Query by committee, linear separation and random walks., On the problem of approximating the number of bases of a matroid, On efficient randomized algorithms for finding the PageRank vector, Similarity of personal preferences: Theoretical foundations and empirical analysis, Randomized interior point methods for sampling and optimization
