New Results in Graph Partitioning and Optimal Inapproximability
sans UGC
This thesis consists of two parts. The first part contains improved
algorithms for graph partitioning problems, both for well-studied
classical problems (Balanced Separator) and for more practically
motivated problems (Identifying Communities). The second part contains
new results towards achieving optimal inapproximability results
without assuming the Unique Games Conjecture.
A. Graph Partitioning
We give the first near-linear time algorithm for Balanced Separator
with the best possible guarantee for spectral algorithms. The
algorithm combines SDP rounding techniques with continuous time random
walks on the graph. We show how to approximate these walks, or
equivalently, the matrix exponential e^{-tL}, where L is the graph
Laplacian, in near-linear time, by combining techniques from
approximation theory and numerical linear algebra.
We give a novel approach to the problem of identifying communities in
a graph representing a social network. We model the network as being
described by overlapping communities with certain local structure; and
under these assumptions, we provably and efficiently recover the
underlying communities.
B. Optimal Inapproximability without assuming UGC
We study the inapproximability of some classic scheduling problems
viz. Concurrent Open Shop and the Assembly Line problem, and prove an
optimal 2-inapproximability for both problems assuming P != NP.
Previously, the best NP-hardness factors known were 6/5 and 1+eps
respectively. We also study the inapproximability of Hypergraph Vertex
Cover on k-uniform k-partite hypergraphs, and prove a nearly optimal
NP-hardness of approximating it within k/2-1, where a
k/2-approximation is known due to Lovász.
The results in this talk are based on joint works with Sanjeev Arora,
Rong Ge, Lorenzo Orecchia, Rishi Saket, Grant Schoenebeck, Madhur
Tulsiani, and Nisheeth K. Vishnoi.