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

In this paper, we develop new tools and connections for exponential timeapproximation. In this setting, we are given a problem instance and a parameter$\alpha>1$, and the goal is to design an $\alpha$-approximation algorithm withthe fastest possible running time. We show the following results:  - An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r\log^2 r+r\log^2r)))$ time,  - An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \logr+r\log^2r)))$ time,  - A $(2-1/r)$-approximation for minimum vertex cover in$O^*(\exp(n/r^{\Omega(r)}))$ time, and  - A $(k-1/r)$-approximation for minimum $k$-hypergraph vertex cover in$O^*(\exp(n/(kr)^{\Omega(kr)}))$ time.  (Throughout, $\tilde O$ and $O^*$ omit $\mathrm{polyloglog}(r)$ and factorspolynomial in the input size, respectively.) The best known time bounds for allproblems were $O^*(2^{n/r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008].For maximum independent set and chromatic number, these bounds werecomplemented by $\exp(n^{1-o(1)}/r^{1+o(1)})$ lower bounds (under theExponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit,2014 (Ph.D. Thesis)]. Our results show that the naturally-looking$O^*(2^{n/r})$ bounds are not tight for all these problems. The key to thesealgorithmic results is a sparsification procedure, allowing the use of betterapproximation algorithms for bounded degree graphs. For obtaining the first tworesults, we introduce a new randomized branching rule.  Finally, we show a connection between PCP parameters and exponential-timeapproximation algorithms. This connection together with our independent setalgorithm refute the possibility to overly reduce the size of Chan's PCP [Chan,2016]. It also implies that a (significant) improvement over our result willrefute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].

New Tools and Connections for Exponential-time Approximation