Lorenzo Orecchia

Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

  • Lorenzo Orecchia
  • Sushant Sachdeva
  • Nisheeth K. Vishnoi
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We give a novel spectral approximation algorithm for the balanced separator problem that, given a graph G, a constant balance b \in (0,1/2], and a parameter \gamma, either finds an \Omega(b)-balanced cut of conductance O(\sqrt{\gamma}) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least \gamma, and runs in … Read more

    A Spectral Algorithm for Improving Graph Partitions

  • Michael W. Mahoney
  • Lorenzo Orecchia
  • Nisheeth K. Vishnoi
    • Categories Approximation Algorithms Tags ,

    In the cut-improvement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any … Read more