The Design of Approximation Algorithms¶
Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.
Cited by¶
4 citations across 4 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Approximation
- Computer science depends on approximation for the intractable: bounded-ratio approximation algorithms for NP-hard problems, as Vazirani (2001) systematizes (Williamson and Shmoys (2011) method
This sourceModern treatment of techniques for designing and analyzing approximation algorithms with guaranteed ratios.
Supported in partVerified against the publisher's abstract
The book's own abstract states that most discrete optimization problems are NP-hard and that it shows how to design approximation algorithms with provable near-optimal guarantees — the NP-hardness/guarantee half of the claim only.
“Yet most such problems are NP-hard; unless P = NP, there are no efficient algorithms to find optimal solutions. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions.”
- Computer science depends on approximation for the intractable: bounded-ratio approximation algorithms for NP-hard problems, as Vazirani (2001) systematizes (Williamson and Shmoys (2011) method
- Scheduling
- T5 — Multi-Objective Conflicts Without Clear Tradeoff Metrics: As Williamson and Shmoys (2011) discuss in their treatment of approximation-algorithm design, minimizing makespan, minimizing weighted tardiness, minimizing flow time, and maximizing utilization or fairness are often conflicting objectives.
This source(Modern consolidated treatment of techniques for designing and analyzing approximation algorithms with guaranteed approximation ratios.)
Supported in partVerified against the publisher's abstract
The book's own publisher description confirms it is a treatment of approximation-algorithm design and names scheduling among its areas, but says nothing about conflicting scheduling objectives or multi-objective tradeoffs.
“This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.”
- T5 — Multi-Objective Conflicts Without Clear Tradeoff Metrics: As Williamson and Shmoys (2011) discuss in their treatment of approximation-algorithm design, minimizing makespan, minimizing weighted tardiness, minimizing flow time, and maximizing utilization or fairness are often conflicting objectives.
Domain-specific¶
- Approximation Algorithm
- L-Reduction
- Standard references formulate the construction in this form and derive its approximation-transfer bounds directly from the two inequalities.
This sourceGives the formal definition, transfer inequalities, and the MAX E3SAT–independent-set and bounded-degree vertex-cover–Steiner-tree examples.
- Standard references formulate the construction in this form and derive its approximation-transfer bounds directly from the two inequalities.
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Read against the text for 2 of 4 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:662a447a127b · see in the full table