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 initiate the systematic study of a recently introduced polynomial-timeanalogue of MaxSNP, which includes a large number of well-studied problems(including Nearest and Furthest Neighbor in the Hamming metric, Maximum InnerProduct, optimization variants of $k$-XOR and Maximum $k$-Cover). Specifically,MaxSP$_k$ denotes the class of $O(m^k)$-time problems of the form$\max_{x_1,\dots, x_k} \#\{y:\phi(x_1,\dots,x_k,y)\}$ where $\phi$ is aquantifier-free first-order property and $m$ denotes the size of the relationalstructure. Assuming central hypotheses about clique detection in hypergraphsand MAX3SAT, we show that for any MaxSP$_k$ problem definable by aquantifier-free $m$-edge graph formula $\phi$, the best possible approximationguarantee in faster-than-exhaustive-search time $O(m^{k-\delta})$ falls intoone of four categories:  * optimizable to exactness in time $O(m^{k-\delta})$,  * an (inefficient) approximation scheme, i.e., a $(1+\epsilon)$-approximationin time $O(m^{k-f(\epsilon)})$,  * a (fixed) constant-factor approximation in time $O(m^{k-\delta})$, or  * an $m^\epsilon$-approximation in time $O(m^{k-f(\epsilon)})$.  We obtain an almost complete characterization of these regimes, for MaxSP$_k$as well as for an analogously defined minimization class MinSP$_k$. As our maintechnical contribution, we rule out approximation schemes for a large class ofproblems admitting constant-factor approximations, under the Sparse MAX3SAThypothesis posed by (Alman, Vassilevska Williams'20). As general trends for theproblems we consider, we find: (1) Exact optimizability has a simple algebraiccharacterization, (2) only few maximization problems do not admit aconstant-factor approximation; these do not even have a subpolynomial-factorapproximation, and (3) constant-factor approximation of minimization problemsis equivalent to deciding whether the optimum is equal to 0.

A Structural Investigation of the Approximability of Polynomial-Time Problems