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, 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 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 MaxSP(_k) problem definable by a quantifier-free (m)-edge graph formula (\phi), the best possible approximation guarantee in faster-than-exhaustive-search time (O(m^{k-\delta})) falls into one of four categories:

• optimizable to exactness in time (O(m^{k-\delta})),
• an (inefficient) approximation scheme, i.e., a ((1+\epsilon))-approximation in 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 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.