Exact Algorithms from FPT Algorithms
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows a concrete way to turn any parameterized or local‑search algorithm running in C^k time into a faster exact algorithm for the full instance: pick a random T‑subset and run monotone local search (only add elements) as an extension problem, yielding a deterministic or randomized N‑time of form (2 − f(C))^n. Gives numbers: 3‑hitting set or 3‑FVS with 3^k becomes ≈1.666^n, min‑ones SAT improves similarly, and derandomization uses small covering families.
AI-written summary · about
chapters (8)
- 0:00Introduction to the topic
- 4:42FPT and exact algorithm link
- 8:57Satisfiability algorithms
- 15:25Permissive local search
- 23:39The extension problem
- 31:00Application examples
- 45:11Counting minimal solutions
- 52:51Philosophical remarks
related talks
34mTesting Intersectingness of Uniform Families or how Dana and I intersected
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
37m"Algorithms" is Not a Four-Letter Word
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
23mAn Algorithmic Bridge Between Hamming and Levenshtein Distances
25mOn computing homological hitting sets
01h 10mComplexity and Algorithmic Game Theory II
52mOn Algorithmic Game Theory I