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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we study the trade-off between the running time ofapproximation algorithms and their approximation guarantees. By leveraging astructure of the `hard' instances of the Arora-Rao-Vazirani lemma [JACM'09], weshow that the Sum-of-Squares hierarchy can be adapted to provide `fast', butstill exponential time, approximation algorithms for several problems in theregime where they are believed to be NP-hard. Specifically, our frameworkyields the following algorithms; here $n$ denote the number of vertices of thegraph and $r$ can be any positive real number greater than 1 (possiblydepending on $n$).  (i) A $\left(2 - \frac{1}{O(r)}\right)$-approximation algorithm for VertexCover that runs in $\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time.  (ii) An $O(r)$-approximation algorithms for Uniform Sparsest Cut, BalancedSeparator, Minimum UnCut and Minimum 2CNF Deletion that runs in$\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time.  Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm[arXiv:1708.03515] which achieves $\left(2 -\frac{1}{O(r)}\right)$-approximation in time$\exp\left(\frac{n}{r^r}\right)n^{O(1)}$. For the remaining problems, ouralgorithms improve upon $O(r)$-approximation$\exp\left(\frac{n}{2^r}\right)n^{O(1)}$-time algorithms that follow from awork of Charikar et al. [SIAM J. Comput.'10].

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems