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

DOI registrant

Springer Nature

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

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? Not recorded. Neither this nor any other of the 3 citations of this work carries a recorded support check.

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.

Registry ID ref:dc650f5c4933 · see in the full table