论文标题
多项式时间问题的近似性的结构研究
A Structural Investigation of the Approximability of Polynomial-Time Problems
论文作者
论文摘要
我们启动了最近引入的MAXSNP多项式类似物的系统研究，其中包括大量研究的问题（包括锤式度量，最大内部产品，最大和最远的邻居，最大的内部产品，$ K $ -XOR的优化变体和最大$ k $ -cover）。具体而言，maxsp $ _k $表示$ o（m^k）$的类 - $ \ max_ {x_1，\ dots，x_k} \ x_k} \ w {n：ϕ（x_1，\ dots，x_1，x_k，x_k，x_k，x_k，x_k，y）\} $ where $ deDEDEDEDERIFER first prorder promeral and $ $ $ $ m的时间问题。假设在HyperGraphs和Max3Sat中进行集团检测的中心假设，我们表明，对于任何MaxSp $ _K $问题，可以通过无量词的$ M $ M $ -EDGE Graph Graph formula $ ϕ $定义，这是更快的exexhan-exexexeardive-search time $ o（m^{k-δ} $ falls of的最佳近似保证 *可以优化到时间$ o（m^{k-δ}）$， *一个（效率低下的）近似方案，即$（1+ε）$ - 时间$ o（m^{k-f（ε）}）$， * a（固定的）恒定因子近似时间$ o（m^{k-δ}）$或 * $ m^ε$ -Approximation in Time $ o（m^{k-f（ε）}）$。 对于MaxSp $ _K $以及类似定义的最小化类Minsp $ _K $，我们几乎完全表征了这些制度。作为我们的主要技术贡献，我们排除了在稀疏的Max3SAT假设下的近似问题的近似方案（Alman，Vassilevska Williams'20）。作为我们考虑的问题的一般趋势，我们发现：（1）精确的优化性具有简单的代数表征，（2）只有少数最大化问题不接受恒定的因子近似；这些甚至没有类别的因子近似，（3）最小化问题的恒定因子近似等同于确定最佳是否等于0。
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:ϕ(x_1,\dots,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 MAX3SAT, 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-δ})$ falls into one of four categories: * optimizable to exactness in time $O(m^{k-δ})$, * an (inefficient) approximation scheme, i.e., a $(1+ε)$-approximation in time $O(m^{k-f(ε)})$, * a (fixed) constant-factor approximation in time $O(m^{k-δ})$, or * an $m^ε$-approximation in time $O(m^{k-f(ε)})$. 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.
