Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator}

Details Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator} Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator}

2009-07-08

arxiv.org/abs/0907.1369v1

Computer Science

Data Structures and Algorithms

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 new family of mathematical programs, which depends upon a parameter $\epsilon > 0$, and extend the seminal work of Arora-Rao-Vazirani ({\sf ARV}) \cite{ARV} to show that the polynomial time solvability of the proposed family of programs implies an improvement in the approximation factor to $O(\log^{{1/3} + \epsilon} n)$ from the best-known factor of $O(\sqrt{\log n})$ due to {\sf ARV}. In fact, for $\epsilon = 1/3$, the program we get is the SDP proposed by {\sf ARV}. For $\epsilon < 1/3$, 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. The properties of concave programs allows one to apply techniques due to Hoffman \cite{H81} or Tuy \emph{et al} \cite{TTT85} to solve such problems with arbitrary accuracy. But the problem of finding of a method to solve these programs that converges in polynomial time still remains open. Our result, although conditional, introduces a new family of programs which is more powerful than semi-definite programming in the context of approximation algorithms and hence it will of interest to investigate this family both in the direction of designing efficient algorithms and proving hardness results.

Affiliated with

Also associated with

No associations

Rating

Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator} 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 Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator}, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator} will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319993