The Design of Approximation Algorithms

Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press.

Type

Book chapter

Intellectual base

Review or monograph

Year

2011

Link

https://www.designofapproxalgs.com/book.pdf

Cited from

mathematics, operations_research

Cited by

4 citations across 4 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Approximation
  • … yields tractable local dynamics, and effective field theories deliver predictions valid at specific energy scales. 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.

• 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.)

Domain-specific

• Approximation Algorithm
  • It addresses problems for which exact optimization is computationally difficult by weakening optimality in a controlled, quantified way rather than abandoning proof.
• 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.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://www.cambridge.org/core/books/design-of-approximation-algorithms/88E0AEAEFF2382681A103EEA572B83C6 ×1

Registry ID ref:662a447a127b · see in the full table