On the Complexity of Computing the Volume of a Polyhedron
From MaRDI portal
Publication:3821581
DOI10.1137/0217060zbMath0668.68049DBLPjournals/siamcomp/DyerF88OpenAlexW1987679122WikidataQ57401617 ScholiaQ57401617MaRDI QIDQ3821581
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217060
Related Items (89)
Computing the Ehrhart polynomial of a convex lattice polytope ⋮ Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies ⋮ A probabilistic interpretation of set-membership filtering: application to polynomial systems through polytopic bounding ⋮ Robust optimal control with adjustable uncertainty sets ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ A Fast and Practical Method to Estimate Volumes of Convex Polytopes ⋮ Estimating the volume of the solution space of SMT(LIA) constraints by a flat histogram method ⋮ A comment on ``Computational complexity of stochastic programming problems ⋮ Exploring stochasticity and imprecise knowledge based on linear inequality constraints ⋮ Polytope Volume Computation ⋮ Computing and estimating the volume of the solution space of SMT(LA) constraints ⋮ A comparison of four approaches from stochastic programming for large-scale unit-commitment ⋮ Some more n‐dimensional geometry† ⋮ Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume ⋮ Expected Number of Vertices of a Hypercube Slice ⋮ Mixed-volume computation by dynamic lifting applied to polynomial system solving ⋮ On the complete instability of interval polynomials ⋮ Approximate counting in SMT and value estimation for probabilistic programs ⋮ Semi-discrete optimal transport: hardness, regularization and numerical solution ⋮ Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space ⋮ Bayesian inference over ICA models: application to multibiometric score fusion with quality estimates ⋮ Computing Galois groups of Ehrhart polynomials in OSCAR ⋮ Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets ⋮ Modeling project preferences in multiattribute portfolio decision analysis ⋮ An algorithm for estimating non-convex volumes and other integrals in \(n\) dimensions ⋮ Markov chains, Hamiltonian cycles and volumes of convex bodies ⋮ Eigenpolytope Universality and Graphical Designs ⋮ Ambiguous Joint Chance Constraints Under Mean and Dispersion Information ⋮ Exploiting sparsity for semi-algebraic set volume computation ⋮ Semiring programming: a semantic framework for generalized sum product problems ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms ⋮ Polar degrees and closest points in codimension two ⋮ Tropical Ehrhart theory and tropical volume ⋮ Exploiting polyhedral symmetries in social choice ⋮ (Deterministic) algorithms that compute the volume of polytopes ⋮ Counting linear extensions ⋮ Probabilistic Lipschitz analysis of neural networks ⋮ A quick estimate for the volume of a polyhedron ⋮ The harmonic polytope ⋮ A tropical isoperimetric inequality ⋮ Polarity and the complexity of the shooting experiment ⋮ Using Histograms to Better Answer Queries to Probabilistic Logic Programs ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ Computing the volume, counting integral points, and exponential sums ⋮ Easy and optimal queries to reduce set uncertainty ⋮ Algorithms for computing centroids ⋮ Aggregate operators in constraint query languages ⋮ Approximating the volume of tropical polytopes is difficult ⋮ Computational complexity of stochastic programming problems ⋮ Approximating the volume of unions and intersections of high-dimensional geometric objects ⋮ Volume Computation for Boolean Combination of Linear Arithmetic Constraints ⋮ On the reverse Loomis-Whitney inequality ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ Polyhedral circuits and their applications ⋮ A practical algorithm for volume estimation based on billiard trajectories and simulated annealing ⋮ Deterministic and randomized polynomial‐time approximation of radii ⋮ Assumed strain methods in micromechanics, laminate composite voxels and level sets ⋮ The moment-SOS hierarchy: applications and related topics ⋮ Local formulas for Ehrhart coefficients from lattice tiles ⋮ Approximation of convex sets by polytopes ⋮ The Santalo point of a planar convex set ⋮ Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy ⋮ Polytopes in the Fiat-Shamir with aborts paradigm ⋮ The best ways to slice a polytope ⋮ How to integrate a polynomial over a simplex ⋮ Unnamed Item ⋮ Projective re-normalization for improving the behavior of a homogeneous conic linear system ⋮ A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor ⋮ Halving the Bounds for the Markov, Chebyshev, and Chernoff Inequalities Using Smoothing ⋮ Energy and reserve dispatch with distributionally robust joint chance constraints ⋮ Complexity of approximating the vertex centroid of a polyhedron ⋮ An algorithm for computing phase space structures in chemical reaction dynamics using Voronoi tessellation ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls ⋮ Worst-Case Expected Shortfall with Univariate and Bivariate Marginals ⋮ A sweep-plane algorithm for generating random tuples in simple polytopes ⋮ Ehrhart polynomials of matroid polytopes and polymatroids ⋮ Uniqueness of Gibbs measures for continuous hardcore models ⋮ Generalized adaptive partition-based method for two-stage stochastic linear programs: geometric oracle and analysis ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes ⋮ Exploiting Symmetries in Polyhedral Computations ⋮ Book Review: Inevitable randomness in discrete mathematics ⋮ Practical volume approximation of high-dimensional convex bodies, applied to modeling portfolio dependencies and financial crises ⋮ Calculating Probabilities of Real-Time Test Cases ⋮ Mathematical programming and the sensitivity of multi-criteria decisions ⋮ Hierarchical clustering of constrained dynamic systems using robust positively invariant sets ⋮ Estimating the volume of solution space for satisfiability modulo linear real arithmetic ⋮ Mean utility in the assurance region model ⋮ Volume of Hypercubes Clipped by Hyperplanes and Combinatorial Identities
This page was built for publication: On the Complexity of Computing the Volume of a Polyhedron
