Geometry, Flows, and Graph-Partitioning Algorithms

Arora, Rao, Vazirani

@article{arora:cacm-2008,
  author={Sanjeev Arora and Satish Rao and Umesh Vazirani},
  title={Scene Completion Using Millions of Photographs},
  journal={Communications of the {ACM}},
  volume={51},
  number={10},
  year={2008}
}

Surveys several developments and approaches to approximate graph partitioning

• Graph partitioning produces a minimal graph cut with balanced components (minimal graph cut by itself generally does not produce balanced trees)

Counterplay between evaluation and fast algorithms

Main approaches based on network flow, cutting congested links