Computer Science – Data Structures and Algorithms
Scientific paper
2010-11-19
Computer Science
Data Structures and Algorithms
Extension of results in authors' previous paper, CoRR abs/0907.1369
Scientific paper
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.
No associations
LandOfFree
Combinatorial Geometry of Graph Partitioning - I does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Combinatorial Geometry of Graph Partitioning - I, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial Geometry of Graph Partitioning - I will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-117148