Complexity and Approximation

Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., & Kann, V. (1999). Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer.

Type

Book

Intellectual base

Review or monograph

Year

1999

DOI

10.1007/978-3-642-58412-1

ISBN

9783642635816

Link

https://doi.org/10.1007/978-3-642-58412-1

Cited by

3 citations across 3 artifacts.

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

Domain-specific

• L-Reduction
  • Standard references formulate the construction in this form and derive its approximation-transfer bounds directly from the two inequalities.

    This sourceAuthoritative monograph on NPO problems, approximation classes, and approximation-preserving reductions.

• Pseudo-polynomial transformation
  • The direction of transfer matters as well: a transformation from a known strongly NP-complete source supports target hardness only when the target is independently shown to lie in the relevant class for completeness.
• PTAS Reduction
  • The Springer monograph Complexity and Approximation treats approximation-preserving reductions as a dedicated toolkit rather than one undifferentiated reducibility relation.

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:dc650f5c4933 · see in the full table