A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
From MaRDI portal
Publication:4698099
DOI10.1287/moor.19.4.769zbMath0821.90085OpenAlexW2129740858MaRDI QIDQ4698099
Publication date: 14 May 1995
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.19.4.769
Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Integer programming (90C10) Computational aspects related to convexity (52B55) Abstract computational complexity for mathematical programming problems (90C60)
Related Items
Sum-integral interpolators and the Euler-Maclaurin formula for polytopes, Integral points in rational polygons: a numerical semigroup approach, Polyhedral omega: a new algorithm for solving linear Diophantine systems, Counting essential surfaces in \(3\)-manifolds, A fixed point iterative approach to integer programming and its distributed computation, On the pseudo-periodicity of the integer hull of parametric convex polygons, Refined upper bounds for the linear Diophantine problem of Frobenius, Column basis reduction and decomposable knapsack problems, Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons, Correlation, partitioning and the probability of casting a decisive vote under the majority rule, Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws, Computing points of bounded height in projective space over a number field, Analyzing the Practical Relevance of the Condorcet Loser Paradox and the Agenda Contraction Paradox, IAC Probability Calculations in Voting Theory: Progress Report, On Dedekind's problem for complete simple games, Lattice-free polytopes and their diameter, The width and integer optimization on simplices with bounded minors of the constraint matrices, Automation of Quantitative Information-Flow Analysis, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, An algebraic-perturbation variant of Barvinok's algorithm, Barvinok's algorithm and the Todd class of a toric variety, Short rational functions for toric algebra and applications, Effective lattice point counting in rational convex polytopes, Computing weight \(q\)-multiplicities for the representations of the simple Lie algebras, How to find the convex hull of all integer points in a polyhedron?, Bias expansion of spatial statistics and approximation of differenced lattice point counts, Computing convex hulls and counting integer points with \texttt{polymake}, Computation of dilated Kronecker coefficients, Exact sampling and counting for fixed-margin matrices, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, Short rational generating functions for solving some families of fuzzy integer programming problems, Asymptotic vulnerability of positional voting rules to coalitional manipulation, Minkowski length of 3D lattice polytopes, Approximate counting in SMT and value estimation for probabilistic programs, On the occurrence probability of local binary patterns: a theoretical study, Experimental Statistics for Mirzakhani’s Theorem, Ehrhart tensor polynomials, Cohomology for Frobenius kernels of \(\mathrm{SL}_2\)., Three Ehrhart quasi-polynomials, Computing Optimized Path Integrals for Knapsack Feasibility, Parametric Presburger arithmetic: complexity of counting and quantifier elimination, Multivariate splines and polytopes, Quantifier elimination for counting extensions of Presburger arithmetic, The generalized Frobenius problem via restricted partition functions, Efficiently testing digital convexity and recognizing digital convex polygons, Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration, An algorithm for the separation of two-row cuts, Monotonicity paradoxes in three-candidate elections using scoring elimination rules, Computing with an algebraic-perturbation variant of Barvinok's algorithm, Integer programming, Barvinok's counting algorithm and Gomory relaxations., An example of probability computations under the IAC assumption: the stability of scoring rules, Unnamed Item, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, Evaluation of Dedekind sums, Eisenstein cocycles, and special values of \(L\)-functions, Eigenvalue distributions of reduced density matrices, A generalization of the integer linear infeasibility problem, Counting Solutions of Integer Programs Using Unrestricted Subtree Detection, Exploiting polyhedral symmetries in social choice, Dedekind-Carlitz polynomials as lattice-point enumerators in rational polyhedra, Precise quantitative information flow analysis -- a symbolic approach, A Euclid style algorithm for MacMahon's partition analysis, A randomized sieving algorithm for approximate integer programming, Computing local zeta functions of groups, algebras, and modules, Enumerating Projections of Integer Points in Unbounded Polyhedra, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, INTERMEDIATE SUMS ON POLYHEDRA: COMPUTATION AND REAL EHRHART THEORY, Counting with rational generating functions, A new complexity result on multiobjective linear integer programming using short rational generating functions, Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra, Non-standard approaches to integer programming, Experiments with the site frequency spectrum, Approximating the volume of tropical polytopes is difficult, The many aspects of counting lattice points in polytopes, Short rational generating functions for lattice point problems, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones., Polyhedral circuits and their applications, Rational polyhedral outer-approximations of the second-order cone, On approximation algorithms for concave mixed-integer quadratic programming, Local formulas for Ehrhart coefficients from lattice tiles, Probabilities of electoral outcomes: from three-candidate to four-candidate elections, Computing the Ehrhart quasi-polynomial of a rational simplex, The $q$-analog of Kostant's partition function and the highest root of the classical Lie algebras, Quasi-polynomials, linear Diophantine equations and semi-linear sets, Efficient Algorithms to Test Digital Convexity, Ehrhart Polynomials and Successive Minima, Reachability analysis of low-order discrete state reaction networks obeying conservation laws, COUNTING NUMERICAL SEMIGROUPS WITH SHORT GENERATING FUNCTIONS, Ehrhart polynomials of matroid polytopes and polymatroids, Unnamed Item, Exploiting Symmetries in Polyhedral Computations, A computational study of integer programming algorithms based on Barvinok's rational functions, Some unexpected properties of Littlewood-Richardson coefficients, Approximating sums by integrals only: multiple sums and sums over lattice polytopes, Computing the integer hull of convex polyhedral sets, Majority properties of positional social preference correspondences, Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases, Values of zeta functions at negative integers, Dedekind sums and toric geometry
