4 The MQI lemma
There is a polynomial time algorithm that answers this decision problem exactly.
Proofs have appeared in at least the following:
-
Uriel Feige and Robert Krauthgamer, A polylogarithmic
approximation of the minimum bisection, FOCS-2000.
- Chris Harrelson, Kirsten Hildrum, and Satish Rao,
A polynomial-time tree decomposition to minimize congestion, SPAA 2003.
The point of this paper is that the algorithm works very well in practice.