文档介绍：IEOR 266, Fall 2003
Graph Algorithms work Flows
Professor Dorit Hochbaum
Contents
1 Introduction 1
Assignment Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Minimum work Flow Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Transportation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Example of general MCNF Problem - the chairs problem . . . . . . . . . . . . . . . . 4
Assigning Individuals to Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Basic graph Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 work Problems 7
Classes work Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
work Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Totally Unimodular Matrices 15
plexity Analysis 17
Measuring Quality of an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Deflnitions for parisons of functions . . . . . . . . . . . . . . . . . . . 19
Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Caveats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A Sketch of the Ellipsoid Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 pleteness 22
Search vs. Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Some Problems in NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Co-NP . . . . . . . . . . . . . . . . . . . . . . . . .