Counting integer points in higher-dimensional polytopes (Q2406337)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting integer points in higher-dimensional polytopes |
scientific article |
Statements
Counting integer points in higher-dimensional polytopes (English)
0 references
27 September 2017
0 references
The paper under review deals with two computational problems concerning convex polyhedra: {\parindent= 0,7cm \begin{itemize}\item[1)] for a convex polyhedron \(P\subset \mathbb R^n\) defined as the intersection of an affine subspace with the non-negative orthant \(\mathbb R^n_+\), compute the number \(| P\cap\mathbb Z^n|\) of integer points in \(P\); \item [2)] for a convex polyhedron \(P\subset \mathbb R^n\) defined as the intersection of an affine subspace with the unit cube \([0,1]^n\), compute the number \(| P\cap\{ 0, 1\}^n|\) of \(0-1\) points in \(P\). \end{itemize}} The author discusses a family of heuristic formulae for computing approximately the desired quantities, which are derived by using an original probabilistic approach, c.f. [the author and \textit{J. A. Hartigan}, Adv. Appl. Math. 45, No. 2, 252--289 (2010; Zbl 1213.05015)]. For the entire collection see [Zbl 1377.52002].
0 references
convex polytope
0 references
integer lattice
0 references
convex optimization
0 references
maximum entropy principle
0 references
anti-concentration inequality
0 references
transportation polytope
0 references
contingency table
0 references