New Results in the Theory of Approximation: Fast Graph Algorithms and Inapproximability

Abstract

For several basic optimization problems, it is <bold>NP</bold>-hard to find an exact solution. As a result, understanding the best possible trade-off between the running time of an algorithm and its approximation guarantee, is a fundamental question in theoretical computer science, and the central goal of the theory of approximation.

There are two aspects to the theory of approximation : (1) efficient approximation algorithms that establish trade-offs between approximation guarantee and running time, and (2) inapproximability results that give evidence against them. In this thesis, we contribute to both facets of the theory of approximation.

In the first part of this thesis, we present the first near-linear-time algorithm for Balanced Separator - given a graph, partition its vertices into two roughly equal parts without cutting too many edges - that achieves the best approximation guarantee possible for algorithms in its class. This is a classic graph partitioning problem and has deep connections to several areas of both theory and practice, such as metric embeddings, Markov chains, clustering, etc.

As an important subroutine for our algorithm for Balanced Separator, we provide a near-linear-time algorithm to simulate the heat-kernel random walk on a graph, equivalent to computing e<super>-L</super>v, where L is the Laplacian of the graph, and v is a vector. This algorithm combines techniques from approximation theory and numerical linear algebra to reduce the problem of approximating the matrix exponential to solving a small number of Laplacian systems. We also give a reduction in the reverse direction, from matrix inversion to matrix exponentiation, hence justifying the use of Laplacian system solvers.

In the second part of this thesis, we prove inapproximability results for several basic optimization problems. We address some classic scheduling problems, <it>viz.</it> Concurrent Open Shop and the Assembly Line problem, and variants of the Hypergraph Vertex Cover problem. For all these problems, optimal inapproximability results were previously known under the Unique Games Conjecture. We are able to prove near-optimal inapproximability results for these problems without using the conjecture.