Fine Grained Approximation Algorithms and Complexity (FG-APX 2019)
May 27-31, 2019
University Residential Center
Bertinoro (Forlì-Cesena), Italy
One of the greatest successes of computational complexity theory is the classification of countless fundamental computational problems into polynomial-time and NP-hard, two classes that are often referred to as tractable and intractable. The young field of Fine-Grained Complexity aims to further classify polynomial time using algorithms, reductions, and new complexity assumptions. Key objects of study include the Strong Exponential Time Hypothesis (SETH), the All-Pairs Shortest Path problem (APSP), and the Matrix Multiplication problem.
University Residential Center
Bertinoro (Forlì-Cesena), Italy
Polynomial time approximability has been proposed as a useful approach to escape the intractability of NP-hard optimization problems. This area has developed into a rich field, with power algorithmic techniques as well as methods for proving hardness of approximation, including the PCP theorem, the Unique Games Conjecture, and the Small-Set Expansion Hypothesis. So far, however, little attention was given to the distinction between the different polynomial runtimes of these approximation algorithms.
This workshop will focus on the intersection of Fine-Grained Complexity and Approximation Algorithms/Hardness of Approximation, that is, on the concrete (polynomial-time) complexity of approximation algorithms. The goal here is to understand possible and impossible tradeoffs between precise polynomial time bounds and precise approximation ratios.