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.

[Joint work with Martin Dyer & Dana Randall]

Lecture #10805

Need help? Visit our help pages at http://www.msri.org/communications/vmath/hints

Streaming Video

This is a high quality streaming video encoded with MPEG-4 and with 640x480 resolution.

Windows and Mac users, QuickTime 6.5 or later required
Linux users, please see our Linux Help Page on how to view our streaming videos

Follow this link to --- Watch the Video Now Via Streaming Video ---

Download QuickTime File

You can download the QuickTime file here. Right click on the link and "Save As..." to save to your local computer.

• 10805-10805-QuickTime.mov (656 MB)

Download MPEG File

You can download the MPEG file here. Right click on the link and "Save As..." to save to your local computer.

• 10805-10805-MPEG-1 DVD.mpg (695 MB)

Create a DVD

You can download the video and audio files here. Please note that you need both files to create a DVD. Right click on the link and "Save As..." to save to your local computer. You can find instructions on how to create a DVD on our help page at http://www.msri.org/communications/vmath/author

• 10805-10805-DVD PCM Audio.aiff (509 MB - Audio Only)
• 10805-10805-MPEG-2 120min High Quality Encode.m2v (1159 MB - Video Only)

Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture.

If you would like to purchase a copy of this video for $15+shipping, please Click Here!

See more of our Streaming Videos on our main VMath - Streaming Video page.