Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration

• 成果类型: Article
• 署名作者: Hirai, Hiroshi; Oshiro, Ryunosuke; Tanaka, Ken'ichiro
• 署名单位: University of Tokyo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.0997
• 发表日期: 2020
• 页码: 455-464
• 关键词: lattice points; algorithm

摘要

In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x is an element of R-m: Ax = y, x >= 0}, where A is an n x in 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, parallel to y parallel to(infinity))(parallel to y parallel to(infinity) + 1)(n)) time and O(poly(n, m, parallel to y parallel to(infinity))) space. This improves, in terms of space complexity, a naive DP algorithm with O((parallel to y parallel to(infinity) + 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, parallel to b parallel to(infinity))(parallel to b parallel to(infinity )+ 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 Bjorklund and Husfeldt.