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

We present a series of almost settled inapproximability results for threefundamental problems. The first in our series is the subexponential-timeinapproximability of the maximum independent set problem, a question studied inthe area of parameterized complexity. The second is the hardness ofapproximating the maximum induced matching problem on bounded-degree bipartitegraphs. The last in our series is the tight hardness of approximating thek-hypergraph pricing problem, a fundamental problem arising from the area ofalgorithmic game theory. In particular, assuming the Exponential TimeHypothesis, our two main results are:  - For any r larger than some constant, any r-approximation algorithm for themaximum independent set problem must run in at least2^{n^{1-\epsilon}/r^{1+\epsilon}} time. This nearly matches the upper bound of2^{n/r} (Cygan et al., 2008). It also improves some hardness results in thedomain of parameterized complexity (e.g., Escoffier et al., 2012 and Chitnis etal., 2013)  - For any k larger than some constant, there is no polynomial time min(k^{1-\epsilon}, n^{1/2-\epsilon})-approximation algorithm for the k-hypergraphpricing problem, where n is the number of vertices in an input graph. Thisalmost matches the upper bound of min (O(k), \tilde O(\sqrt{n})) (by Balcan andBlum, 2007 and an algorithm in this paper).  We note an interesting fact that, in contrast to n^{1/2-\epsilon} hardnessfor polynomial-time algorithms, the k-hypergraph pricing problem admitsn^{\delta} approximation for any \delta >0 in quasi-polynomial time. This putsthis problem in a rare approximability class in which approximabilitythresholds can be improved significantly by allowing algorithms to run inquasi-polynomial time.

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses