Roughgarden T. Algorithms Illuminated (Part 4): Algorithms for NP-Hard Problems

New York: Soundlikeyourself Publishing, 2020. — 271 p.What Is NP-Hardness?
MST vs. TSP: An Algorithmic Mystery
Possible Levels of Expertise
Easy and Hard Problems
Algorithmic Strategies for NP-Hard Problems
Proving NP-Hardness: A Simple Recipe
Rookie Mistakes and Acceptable InaccuraciesCompromising on Correctness: Efficient Inexact Algorithms
Makespan Minimization
Maximum Coverage
Influence Maximization
The 2-OPT Heuristic Algorithm for the TSP
Principles of Local SearchCompromising on Speed: Exact Inefficient Algorithms
The Bellman-Held-Karp Algorithm for the TSP
Finding Long Paths by Color Coding
Problem-Specific Algorithms vs. Magic Boxes
Mixed Integer Programming Solvers
Satisfiability SolversProving Problems NP-Hard
Reductions Revisited
3-SAT and the Cook-Levin Theorem
The Big Picture
A Template for Reductions
Independent Set Is NP-Hard
Directed Hamiltonian Path Is NP-Hard
The TSP Is NP-Hard
Subset Sum Is NP-HardP, NP, and All That
Amassing Evidence of Intractability
Decision, Search, and Optimization
NP: Problems with Easily Recognized Solutions
The P=NP Conjecture
The Exponential Time Hypothesis
NP-CompletenessCase Study: The FCC Incentive Auction
Repurposing Wireless Spectrum
Greedy Heuristics for Buying Back Licenses
Feasibility Checking
Implementation as a Descending Clock Auction
The Final OutcomeEpilogue: A Field Guide to Algorithm Design
Hints and Solutions