
arXiv: 1807.05348
In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x ∈ Rm: Ax = 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 [Formula: see text] time and [Formula: see text] space. This improves, in terms of space complexity, a naive DP algorithm with [Formula: see text]-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 [Formula: see text] 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.
FOS: Computer and information sciences, trapezoidal rule, Discrete Mathematics (cs.DM), \(Z\)-transformation, Hypergraphs, 510, integer points in polytopes, Special polytopes (linear programming, centrally symmetric, etc.), Numerical integration, numerical integration, FOS: Mathematics, counting algorithm, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, trapezoidal rule, Discrete Mathematics (cs.DM), \(Z\)-transformation, Hypergraphs, 510, integer points in polytopes, Special polytopes (linear programming, centrally symmetric, etc.), Numerical integration, numerical integration, FOS: Mathematics, counting algorithm, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
