Counting Integer Points in Higher-Dimensional Polytopes

被引：4
|
作者：
Barvinok, Alexander [1 ]
机构：
[1] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA
来源：
CONVEXITY AND CONCENTRATION | 2017年 / 161卷
关键词：
ASYMPTOTIC ENUMERATION; PRESCRIBED ROW; MATRICES; NUMBER; GRAPHS; TABLE;
D O I：
10.1007/978-1-4939-7005-6_20
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We survey some computationally efficient formulas to estimate the number of integer or 0-1 points in polytopes. In many interesting cases, the formulas are asymptotically exact when the dimension of the polytopes grows. The polytopes are defined as the intersection of the non-negative orthant or the unit cube with an affine subspace, while the main ingredient of the formulas comes from solving a convex optimization problem on the polytope.
引用
收藏
页码：585 / 612
页数：28
相关论文
共 50 条
  • [1] Counting Integer Points of Flow Polytopes
    Kabir Kapoor
    Karola Mészáros
    Linus Setiabrata
    Discrete & Computational Geometry, 2021, 66 : 723 - 736
  • [2] Counting Integer Points of Flow Polytopes
    Kapoor, Kabir
    Meszaros, Karola
    Setiabrata, Linus
    DISCRETE & COMPUTATIONAL GEOMETRY, 2021, 66 (02) : 723 - 736
  • [3] Polygons as sections of higher-dimensional polytopes
    Padrol, Arnau
    Pfeifle, Julian
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (01):
  • [4] Counting integer points in polytopes associated with directed graphs
    Fischer, Ilse
    ADVANCES IN APPLIED MATHEMATICS, 2016, 79 : 125 - 153
  • [5] Counting the Integer Points of Parametric Polytopes: A Maple Implementation
    Jing, Rui-Juan
    Lei, Yuzhuo
    Maligec, Christopher F. S.
    Maza, Marc Moreno
    COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING, CASC 2024, 2024, 14938 : 140 - 160
  • [6] Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions
    Sven Verdoolaege
    Rachid Seghir
    Kristof Beyls
    Vincent Loechner
    Maurice Bruynooghe
    Algorithmica, 2007, 48 : 37 - 66
  • [7] Counting integer points in parametric polytopes using Barvinok's rational functions
    Verdoolaege, Sven
    Seghir, Rachid
    Beyls, Kristof
    Loechner, Vincent
    Bruynooghe, Maurice
    ALGORITHMICA, 2007, 48 (01) : 37 - 66
  • [8] An algorithm for counting arcs in higher-dimensional projective space
    Isham, Kelly
    FINITE FIELDS AND THEIR APPLICATIONS, 2022, 80
  • [9] VORONOI DIAGRAMS OF MOVING POINTS IN HIGHER-DIMENSIONAL SPACES
    ALBERS, G
    ROOS, T
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 621 : 399 - 409
  • [10] Stationary amplitudes of quantum walks on the higher-dimensional integer lattice
    Komatsu, Takashi
    Konno, Norio
    QUANTUM INFORMATION PROCESSING, 2017, 16 (12)
12345