Fast Unimodular Counting
JOHN MOUNT
Source record
Source: Crossref
Published: May 1, 2000
DOI: 10.1017/s0963548300004193
Open original source ↗Source abstract
This paper describes methods for counting the number of nonnegative integer solutions of the system Ax = b when A is a nonnegative totally unimodular matrix and b an integral vector of fixed dimension. The complexity (under a unit cost arithmetic model) is strong in the sense that it depends only on the dimensions of A and not on the size of the entries of b . For the special case of ‘contingency tables’ the run-time is 2 O (√ d log d ) (where d is the dimension of the polytope). The method is complementary to Barvinok's in that our algorithm is effective on problems of high dimension with a fixed number of (non-sign) constraints, whereas Barvinok's algorithms are effective on problems of low dimension and an arbitrary number of constraints.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.