CS261 Lecture 16: Multicommodity flow

In which we define a multi-commodity flow problem, and we see that its dual is the relaxation of a useful graph partitioning problem. The relaxation can be rounded to yield an approximate graph partitioning algorithm.

Continue reading

Advertisements