2022/04/25 by Karl Bringmann, Alejandro Cassis, Bringmann, Karl +5
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.2204.11681
Appears at ICALP '22, abstract shortened to fit arXiv requirements
arxiv created 2022/04/25 · arxiv updated 2022/04/26
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, MaxSPk denotes the class of O(mk)-time problems of the form maxx1,…, xk #\y:ϕ(x1,…,xk,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 MAX3SAT, we show that for any MaxSPk problem definable by a quantifier-free m-edge graph formula ϕ, the best possible approximation guarantee in faster-than-exhaustive-search time O(mk-δ) falls into one of four categories: * optimizable to exactness in time O(mk-δ), * an (inefficient) approximation scheme, i.e., a (1+ε)-approximation in time O(mk-f(ε)), * a (fixed) constant-factor approximation in time O(mk-δ), or * an mε-approximation in time O(mk-f(ε)). We obtain an almost complete characterization of these regimes, for MaxSPk as well as for an analogously defined minimization class MinSPk. As our main technical contribution, we rule out approximation schemes for a large class of problems admitting constant-factor approximations, under the Sparse MAX3SAT hypothesis posed by (Alman, Vassilevska Williams'20). As general trends for the problems we consider, we find: (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.