Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc
  Balanced Separator}   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.

33
The categories of this paper are: plasm-ph
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex
8
The categories of this paper are: hep-ex
24
The categories of this paper are: dg-ga
20
The categories of this paper are: acc-phys
37
The categories of this paper are: supr-con
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
18
The categories of this paper are: econ
27
The categories of this paper are: comp-gas
4
The categories of this paper are: cond-mat
30
The categories of this paper are: q-alg
22
The categories of this paper are: chao-dyn
29
The categories of this paper are: funct-an