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

DOI registrant

Springer Nature

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.

    Supported in partVerified against the publisher's abstract

    The abstract establishes that NP-hard problems make polynomial-time approximation a compelling subject in computer science; it carries none of the claim's physics clauses.

    “Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conjecture that P≠NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial-time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics.”

    Read by an automated reader; not a human review. How support was checked

• 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

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 3 citations: 1 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.

• https://doi.org/10.1007/978-3-662-04565-7 ×1

Registry ID ref:fabb0f55d14a · see in the full table