Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration

Hiroshi Hirai (), Ryunosuke Oshiro () and Ken’ichiro Tanaka ()
Additional contact information
Hiroshi Hirai: Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan
Ryunosuke Oshiro: Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan
Ken’ichiro Tanaka: Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan

Mathematics of Operations Research, 2020, vol. 45, issue 2, 455-464

Abstract: In this paper, we address the problem of counting integer points in a rational polytope described by P ( y ) = { x ∈ R m : A x = y, x ≥ 0}, where A is an n × m integer matrix and y is an n -dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P ( y ) can be computed in O ( poly ( n , m , ‖ y ‖ ∞ ) ( ‖ y ‖ ∞ + 1 ) n ) time and O ( poly ( n , m , ‖ y ‖ ∞ ) ) space. This improves, in terms of space complexity, a naive DP algorithm with O ( ( ‖ y ‖ ∞ + 1 ) n ) -size dynamic programming table. Our result is based on the standard error analysis of the numerical contour integration for the inverse Z transform and establishes a new type of an inclusion-exclusion formula for integer points in P ( y ).

We apply our result to hypergraph b -matching and obtain a O ( poly ( n , m , ‖ b ‖ ∞ ) ( ‖ b ‖ ∞ + 1 ) ( 1 − 1 / k ) n ) time algorithm for counting b -matchings in a k -partite hypergraph with n vertices and m hyperedges. This result is viewed as a b -matching generalization of the classical result by Ryser for k = 2 and its multipartite extension by Björklund and Husfeldt.

Keywords: integer points in polytopes; counting algorithm; Z-transformation; numerical integration; trapezoidal rule (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0997 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:2:p:455-464

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().