Hostname: page-component-7c8c6479df-ph5wq Total loading time: 0 Render date: 2024-03-29T09:08:15.078Z Has data issue: false hasContentIssue false

Fast Unimodular Counting

Published online by Cambridge University Press:  01 May 2000

JOHN MOUNT
Affiliation:
@TheMoment, Inc., 2755 Campus Dr., Suite 145, San Mateo, CA 94403, USA (e-mail: ja_mount@pacbell.net)

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 2O(√dlogd) (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.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)