A Structural Investigation of the Approximability of Polynomial-Time Problems

An extensive research effort targets optimal (in)approximability results for various NP-hard optimization problems. Notably, the works of (Creignou'95) as well as (Khanna, Sudan, Trevisan, Williamson'00) establish a tight characterization of a large subclass of MaxSNP, namely Boolean MaxCSPs and further variants, in terms of their polynomial-time approximability. Can we obtain similarly encompassing characterizations for classes of polynomial-time optimization problems?
To this end, we initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of $k$-XOR and Maximum $k$-Cover). Specifically, for each $k$, MaxSP${}_k$ denotes the class of $O(m^k)$-time problems of the form max${}_{x_1,\dots ,x_k}$ #{$y:\varphi$$(x_1$,…,$x_{k,y})$ where ϕ is a quantifier-free first-order property and m denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and exact Max-3-SAT, we show that for any MaxSP${}_k$ problem definable by a quantifier-free m-edge graph formula φ, the best possible approximation guarantee in faster-than-exhaustive-search time $O(m^{k-\delta })$falls into one of four categories:
... mehr
- optimizable to exactness in time $O(m^{k-\delta })$,
- an (inefficient) approximation scheme, i.e., a (1+ε)-approximation in time $O(m^{k-f(\epsilon )})$,
- a (fixed) constant-factor approximation in time $O(m^{k-\delta })$, or
- a nm^ε-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 main technical contribution, we show how to rule out the existence of approximation schemes for a large class of problems admitting constant-factor approximations, under a hypothesis for exact Sparse Max-3-SAT algorithms posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we observe: (1) Exact optimizability has a simple algebraic characterization, (2) only few maximization problems do not admit a constant-factor approximation; these do not even have a subpolynomial-factor approximation, and (3) constant-factor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.