Previous Up Next

8  How to fool it

Actually, the MQI subroutine cannot be fooled. In the worst case, it gets exactly the right answer.

However, the overall heuristic method of (bisection proposer)+MQI can be fooled. Just build the cartesion product of a graph with a good bisection and a graph with a better 1/3-balance quotient cut. One can arrange for the result to be any factor worse than the optimum.




Previous Up Next