Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-184 | 19th November 2010 18:22

Combinatorial Geometry of Graph Partitioning - I


Authors: Manjish Pal
Publication: 28th November 2010 08:47
Downloads: 2247


The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced Separator} problem. More
specifically, we propose a family of mathematical programs, that depend upon a
parameter $p > 0$, and is an extension of the uniform version of the SDPs proposed by Goemans and Linial for this problem. In fact for the case, when $p=1$, if one can solve this program in polynomial time then simply using the
Goemans-Williamson's randomized rounding algorithm for {\sc Max Cut} \cite{WG95} will give an $O(1)$-factor approximation algorithm for {\sc $c$-Balanced Separator} improving the best known approximation factor of
$O(\sqrt{\log n})$ due to Arora, Rao and Vazirani \cite{ARV}. This family of
programs is not convex but one can transform them into so called \emph{\textbf{concave programs}} in which one optimizes a concave function over a convex feasible set. It is well known that the optima of such programs lie at
one of the extreme points of the feasible set \cite{TTT85}. Our main
contribution is a combinatorial characterization of some extreme points of the
feasible set of the mathematical program, for $p=1$ case, which to the best of
our knowledge is the first of its kind. We further demonstrate how this
characterization can be used to solve the program in a restricted setting.
Non-convex programs have recently been investigated by Bhaskara and
Vijayaraghvan \cite{BV11} in which they design algorithms for approximating
Matrix $p$-norms although their algorithmic techniques are analytical in

ISSN 1433-8092 | Imprint