Fine-Grained Complexity of Optimization Problems

IGAFIT ALGORITHMIC COLLOQUIUM 11 Karl Bringmann, Saarland University, April 8, 2021 Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on conjectures such as the Strong Exponential Time Hypothesis. This enables the design of “best-possible” algorithms, where the running time of the algorithm matches a conditional lower bound. This talk surveys the developments of fine-grained complexity on classic optimization problems such as Subset Sum. In particular, since recently we know a best-possible algorithm for solving Subset Sum in pseudopolynomial time. We survey this result and the subsequent developments on approximation algorithms, output sensitive algorithms, and pseudopolynomial algorithms under different parameters. We also discuss extensions to other optimization problems such as Knapsack and Partition, scheduling, and integer linear programming.