main page — CS 627 Advanced Algorithms
Unit 6: Advanced Parameterized Ideas
This unit covers
- linear programming
- LP-based FPT algorithms
- lower bounds based on the Exponential Time Hypothesis (ETH)
Material
- slides
- Video 6-1 (2025-06-03):
Linear programs for modeling problems
- Video 6-2 (2025-06-03):
Linear program normal forms
- Video 6-3 (2025-06-03):
The simplex algorithm
- Video 6-4 (2025-06-04):
Integer programs
- Video 6-5 (2025-06-04):
LP-based kernelization
- Video 6-6 (2025-06-04):
Lower bounds based on the Exponential Time Hypothesis (ETH)
- Video 6-7 (2025-06-10):
Lower bounds based on the Exponential Time Hypothesis (ETH) part 2
Further reading and sources
The introduction to linear programming is based on various (formal and informal) sources; the most relevant ones are here:
- J. Erickson: Algorithms H Linear Programming
- J. Erickson: Algorithms I Linear Programming Algorithms
- H. W. Hamacher, K. Klamroth: Lineare Optimierung und Netzwerkoptimierung (2nd ed)
This book is in German and English (every page is a split screen with both languages).
The lower bound examples based on (S)ETH are taken from
- M. Cygan et al. (2015): Parameterized Algorithms