CMU-CS-12-121Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-12-121
Ali Kemal Sinop May 2012 Ph.D. Thesis
Keywords:
Approximation algorithms, certificate of infeasibility, column selection,
graph partitioning, graph spectrum, Lasserre hierarchy, local rounding,
semi-definite programming, strong duality
Graph partitioning is a fundamental optimization problem that has
been intensively studied. Many graph partitioning formulations are
important as building blocks for divide-and-conquer algorithms on
graphs as well as to many applications such as VLSI layout, packet
routing in distributed networks, clustering and image segmentation.
Unfortunately such problems are notorious for the huge gap between
known best known approximation algorithms and hardness of approximation
results. In this thesis, we study approximation algorithms for
graph partitioning problems using a strong hierarchy of relaxations
based on semi-definite programming, called Our main contribution in this thesis is a propagation based rounding framework for solutions arising from such relaxations. We present a novel connection between the quality of solutions it outputs and column based matrix reconstruction problem. As part of our work, we derive optimal bounds on the number of columns necessary together with efficient randomized and deterministic algorithms to find such columns. Using this framework, we derive approximation schemes for many graph partitioning problems with running times dependent on how fast the graph spectrum grows.
Our final contribution is a fast SDP solver for this rounding framework:
Even though SDP relaxation has 2 poly^{O(r)}(n)
by only partially solving the
relevant part of relaxation. In order to achieve this, we present a new
ellipsoid algorithm that returns certificate of infeasibility
175 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |