main page — CS 627 Advanced Algorithms
Unit 6: Advanced Parameterized Ideas
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
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, 33:37):
Linear programs for modeling problems
- Video 6-2 (2025-06-03, 11:33):
Linear program normal forms
- Video 6-3 (2025-06-03, 25:32):
The simplex algorithm
- Video 6-4 (2025-06-04, 17:48):
Integer programs
- Video 6-5 (2025-06-04, 39:04):
LP-based kernelization
- Video 6-6 (2025-06-04, 19:30):
Lower bounds based on the Exponential Time Hypothesis (ETH)
- Video 6-7 (2025-06-10, 27:44):
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