Abstract
An extensive research effort targets optimal (in)approximability results for various NPhard 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 polynomialtime approximability. Can we obtain similarly encompassing characterizations for classes of polynomialtime optimization problems?
To this end, we initiate the systematic study of a recently introduced polynomialtime analogue of MaxSNP, which includes a large number of wellstudied problems (including Nearest and Furthest Neighbor in the Hamming metric, Maximum Inner Product, optimization variants of kXOR and Maximum kCover). Specifically, for each k, MaxSP_k denotes the class of O(m^k)time problems of the form max_{x_1,… , x_k} #{y : ϕ(x_1,… ,x_k,y)} where ϕ is a quantifierfree firstorder property and m denotes the size of the relational structure. Assuming central hypotheses about clique detection in hypergraphs and exact Max3SAT}, we show that for any MaxSP_k problem definable by a quantifierfree medge graph formula φ, the best possible approximation guarantee in fasterthanexhaustivesearch 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^{kf(ε)}),
 a (fixed) constantfactor approximation in time O(m^{kδ}), or
 a nm^εapproximation in time O(m^{kf(ε)}).
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 constantfactor approximations, under a hypothesis for exact Sparse Max3SAT 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 constantfactor approximation; these do not even have a subpolynomialfactor approximation, and (3) constantfactor approximation of minimization problems is equivalent to deciding whether the optimum is equal to 0.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.ICALP.2022.30,
author = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and K\"{u}nnemann, Marvin},
title = {{A Structural Investigation of the Approximability of PolynomialTime Problems}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {30:130:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16371},
URN = {urn:nbn:de:0030drops163713},
doi = {10.4230/LIPIcs.ICALP.2022.30},
annote = {Keywords: Classification Theorems, Hardness of Approximation in P, Finegrained Complexity Theory}
}
Keywords: 

Classification Theorems, Hardness of Approximation in P, Finegrained Complexity Theory 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 