On the Complexity of Computing the Volume of a Polyhedron
From MaRDI portal
Publication:3821581
DOI10.1137/0217060zbMath0668.68049OpenAlexW1987679122WikidataQ57401617 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
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, 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, 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, Deterministic and randomized polynomial‐time approximation of radii, Local formulas for Ehrhart coefficients from lattice tiles, Approximation of convex sets by polytopes, The Santalo point of a planar convex set, 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
