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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references