Lectures on Proof Verification and Approximation Algorithms

Jansen, T. (1998). Lectures on Proof Verification and Approximation Algorithms. Springer.

Type

Book

Intellectual base

Review or monograph

Year

1998

DOI

10.1007/bfb0053011

Link

https://doi.org/10.1007/bfb0053011

Cited by

1 citation across 1 artifact.

Domain-specific

• Fully polynomial-time approximation scheme
  • For each epsilon greater than zero an FPTAS returns a feasible solution within the declared multiplicative or additive guarantee, and unlike a general PTAS cannot hide superpolynomial dependence on one over epsilon.

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.

Registry ID ref:708a6bf918b8 · see in the full table