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

Description

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