  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.
