License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.9
URN: urn:nbn:de:0030-drops-147024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14702/
Bringmann, Karl ;
Cassis, Alejandro ;
Fischer, Nick ;
Künnemann, Marvin
Fine-Grained Completeness for Optimization in P
Abstract
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time 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 MaxSNP-completeness for NP optimization problems (Papadimitriou, Yannakakis, JCSS 1991), we define polynomial-time 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 k-XOR 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 quantifier-free first-order property over a given relational structure (with MinSP defined analogously). On m-sized 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 fine-grained 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 c-approximation 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 faster-than-O(m^{k+?-1}) time.
- By fine-tuning 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 = {{Fine-Grained Completeness for Optimization in P}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {9:1--9:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14702},
URN = {urn:nbn:de:0030-drops-147024},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.9},
annote = {Keywords: Fine-grained Complexity \& Algorithm Design, Completeness, Hardness of Approximation in P, Dimensionality Reductions}
}
|
Keywords: |
|
Fine-grained Complexity & Algorithm Design, Completeness, Hardness of Approximation in P, Dimensionality Reductions |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
