Approximation Algorithms

Vazirani, V. V. (2001). Approximation Algorithms. Springer.

Type

Book

Intellectual base

Review or monograph

Year

2001

DOI

10.1007/978-3-662-04565-7

ISBN

9783540653677

Link

https://link.springer.com/book/10.1007/978-3-662-04565-7

Cited from

mathematics

Cited by

3 citations across 3 artifacts.

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

Primes

• Approximation
  • In physics, perturbation theory expands around solvable cases (harmonic oscillator, hydrogen atom), linearization around equilibria 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

    This sourceComprehensive treatment of bounded-ratio approximation for NP-hard problems.

• Optimization
  • The two combine in approximation algorithms — bounded-ratio solvers for NP-hard problems

    This source(Comprehensive treatment of bounded-ratio approximation for NP-hard problems.).

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.

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://doi.org/10.1007/978-3-662-04565-7 ×1

Registry ID ref:fabb0f55d14a · see in the full table