Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Approximately Counting Integral Flows and Cell-Bounded Contingency Tables
Authors: Mary Cryan ; Martin Dyer ; Dana Randall
Date:May 2005
Publication Title:Proceedings of STOC 2005 (Symposium on the Theory of Computing)
Publication Type:Conference Paper Publication Status:Published
Page Nos:413-422
DOI:10.1145/1060590.1060652 ISBN/ISSN:1-158113-9
We consider the problem of approximately counting integral flows in a network. We show that there is an fpras based on volume estimation if all capacities are sufficiently large, generalising a result of Dyer, Kannan and Mount (1997). We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums and cell bounds may be arbitrary. We provide an fpras for this problem via a combination of dynamic programming and volume estimation. This generalises an algorithm of Cryan and Dyer (2002) for standard contingency tables, but the analysis here is considerably more intricate.
Links To Paper
This is the ACM (publisher) webpage for the paper.
Mary Cryan's webpage, which has a copy of the paper.
Bibtex format
author = { Mary Cryan and Martin Dyer and Dana Randall },
title = {Approximately Counting Integral Flows and Cell-Bounded Contingency Tables},
book title = {Proceedings of STOC 2005 (Symposium on the Theory of Computing)},
publisher = {ACM},
year = 2005,
month = {May},
pages = {413-422},
doi = {10.1145/1060590.1060652},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh