Previous Up Next

2  Graph Partitioning Methods

Graph partitioning is NP-hard. Many approximate methods have been proposed.
  1. Theoretical Algorithms [relaxations of QIP (min xTLx; xi in {-1,1}; xTe = 0)]
    1. Spectral 1985 (QP) (opt*opt)
    2. Leighton-Rao 1988 (LP, multicommodity flow) (opt * log n)
    3. Arora-Rao-Vazirani 2004 (SDP) (opt * sqrt(log n))
  2. Methods that aim for practicality rather than provability.
    1. Hill-climbing, simulated annealing, tabu search, etc.
    2. Kernighan-Lin / Fiduccia-Matheyses
    3. Multi-resolution FM (Metis)
    4. Metis+MQI (flow-based, this talk)
Previous Up Next