Pseudopolynomial-Time Algorithms for Optimization Problems

Explore fine-grained complexity theory and its applications to classic discrete optimization problems in this comprehensive lecture by Karl Bringmann. Delve into the design of "best-possible" algorithms, focusing on the Subset Sum problem and its optimal solution in terms of target value. Examine subsequent developments in various parameterizations of Subset Sum and other optimization challenges, including Knapsack, Partition, Bicriteria Path, scheduling, and integer linear programming. Learn about conditional lower bounds, average free sets, reductions, polyend factors, color coding techniques, and approximation schemes while gaining insights into the cutting-edge research in theoretical computer science.

Intro
Conditional lower bounds
Average free sets
Reduction
Polyend factors
Subset sum
Color coding
Large and small items
Generalizations
Other Parameters
Curious Parameters
Knapsack
Approximation Schemes