- Abstract:
-
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
- @InProceedings{EDI-INF-RR-0468,
- 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 = {http://portal.acm.org/citation.cfm?id=1060590.1060652&coll=portal&dl=ACM&type=series&idx=1060590&part=Proceedings&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=58893700&CFTOKEN=94022534},
- }
|
