Fourth book in a series that provides an accessible, no-nonsense, and programming language-agnostic introduction to algorithms. Includes hints or solutions to all quizzes and problems, and a series of YouTube videos by the author accompanies the book. Part 4 covers algorithmic tools for tackling NP-hard problems (heuristic algorithms, local search, dynamic programming, MIP and SAT solvers) and techniques for quickly recognizing NP-hard problems in the wild.
Author(s): Tim Roughgarden
Edition: 1
Publisher: Soundlikeyourself Publishing, LLC
Year: 2020
Language: English
Commentary: Vector PDF
Pages: 271
City: New York, NY
Tags: Algorithms; Algorithms Design Techniques; Algorithm Analysis; NP-Hardness
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
