Expander Flows, Geometric Embeddings and Graph Partitioning

摘要

Abstract. We give a O (Vlog~(1/2)n)-approximation algorithm for the SPARSEST CUT, EDGE EXPANSION, balanced separator, and graph conductance problems. This improves the O(logn)-approxima-tion of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in R~d, whose proof makes essential use of a phenomenon called measure concentration.rnWe also describe an interesting and natural "approximate certificate" for a graph's expansion, which involves embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.