Roughgarden T Algorithms Illuminated Part 4 2020

Textbook in PDF format

Preface
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 Inaccuracies
Problems
Compromising on Correctness: Efficient Inexact Algorithms
Makespan Minimization
Maximum Coverage
Influence Maximization
The 2-OPT Heuristic Algorithm for the TSP
Principles of Local Search
Problems
Compromising 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 Solvers
Problems
Proving 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-Hard
Problems
P, 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-Completeness
Problems
Case Study: The FCC Incentive Auction
Repurposing Wireless Spectrum
Greedy Heuristics for Buying Back Licenses
Feasibility Checking
Implementation as a Descending Clock Auction
The Final Outcome
Problems
Epilogue: A Field Guide to Algorithm Design
Hints and Solutions
Index