English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem inwhich given a graph $G$, one aims to find a cut of minimum size such that boththe sides of the cut have at least $cn$ vertices. In this paper, we present newdirections of progress in the {\sc $c$-Balanced Separator} problem. Morespecifically, we propose a new family of mathematical programs, which dependsupon a parameter $\epsilon > 0$, and extend the seminal work ofArora-Rao-Vazirani ({\sf ARV}) \cite{ARV} to show that the polynomial timesolvability of the proposed family of programs implies an improvement in theapproximation factor to $O(\log^{{1/3} + \epsilon} n)$ from the best-knownfactor 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$, thisfamily of programs is not convex but one can transform them into so called\emph{\textbf{concave programs}} in which one optimizes a concave function overa convex feasible set. The properties of concave programs allows one to applytechniques due to Hoffman \cite{H81} or Tuy \emph{et al} \cite{TTT85} to solvesuch problems with arbitrary accuracy. But the problem of finding of a methodto solve these programs that converges in polynomial time still remains open.Our result, although conditional, introduces a new family of programs which ismore powerful than semi-definite programming in the context of approximationalgorithms and hence it will of interest to investigate this family both in thedirection of designing efficient algorithms and proving hardness results.

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