__
TR10-184 | 19th November 2010 18:22
__

#### Combinatorial Geometry of Graph Partitioning - I

**Abstract:**
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

nature.