Bringmann, Karl ;
Cassis, Alejandro ;
Fischer, Nick ;
Künnemann, Marvin
FineGrained Completeness for Optimization in P
Abstract
We initiate the study of finegrained completeness theorems for exact and approximate optimization in the polynomialtime regime.
Inspired by the first completeness results for decision problems in P (Gao, Impagliazzo, Kolokolova, Williams, TALG 2019) as well as the classic class MaxSNP and MaxSNPcompleteness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomialtime analogues MaxSP and MinSP, which contain a number of natural optimization problems in P, including Maximum Inner Product, general forms of nearest neighbor search and optimization variants of the kXOR problem. Specifically, we define MaxSP as the class of problems definable as max_{x₁,… ,x_k} #{(y₁,… ,y_𝓁) : ϕ(x₁,… ,x_k, y₁,… ,y_𝓁)}, where ϕ is a quantifierfree firstorder property over a given relational structure (with MinSP defined analogously). On msized structures, we can solve each such problem in time O(m^{k+𝓁1}). Our results are:
 We determine (a sparse variant of) the Maximum/Minimum Inner Product problem as complete under deterministic finegrained reductions: A strongly subquadratic algorithm for Maximum/Minimum Inner Product would beat the baseline running time of O(m^{k+𝓁1}) for all problems in MaxSP/MinSP by a polynomial factor.
 This completeness transfers to approximation: Maximum/Minimum Inner Product is also complete in the sense that a strongly subquadratic capproximation would give a (c+ε)approximation for all MaxSP/MinSP problems in time O(m^{k+𝓁1δ}), where ε > 0 can be chosen arbitrarily small. Combining our completeness with (Chen, Williams, SODA 2019), we obtain the perhaps surprising consequence that refuting the OV Hypothesis is equivalent to giving a O(1)approximation for all MinSP problems in fasterthanO(m^{k+𝓁1}) time.
 By finetuning our reductions, we obtain mild algorithmic improvements for solving and approximating all problems in MaxSP and MinSP, using the fastest known algorithms for Maximum/Minimum Inner Product.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.APPROX/RANDOM.2021.9,
author = {Bringmann, Karl and Cassis, Alejandro and Fischer, Nick and K\"{u}nnemann, Marvin},
title = {{FineGrained Completeness for Optimization in P}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {9:19:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14702},
URN = {urn:nbn:de:0030drops147024},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.9},
annote = {Keywords: Finegrained Complexity \& Algorithm Design, Completeness, Hardness of Approximation in P, Dimensionality Reductions}
}
15.09.2021
Keywords: 

Finegrained Complexity & Algorithm Design, Completeness, Hardness of Approximation in P, Dimensionality Reductions 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Issue date: 

2021 
Date of publication: 

15.09.2021 