Pseudopolynomial-Time Algorithms for Optimization Problems

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.