A Short Guide to Approximation Preserving Reductions

Crescenzi, P. (1997). A Short Guide to Approximation Preserving Reductions. Proceedings of the 12th Annual IEEE Conference on Computational Complexity, 262-273.

Type

Conference paper

Intellectual base

Primary research

Year

1997

Pages

262-273

DOI

10.1109/ccc.1997.612321

DOI registrant

Institute of Electrical and Electronics Engineers

Link

https://doi.org/10.1109/CCC.1997.612321

Cited by

2 citations across 2 artifacts.

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

Domain-specific

• L-Reduction
  • Crescenzi's survey compares these reducibilities and emphasizes that the choice of reduction controls what consequence is licensed.

    This sourceReviews competing reducibilities and their proof uses.

• PTAS Reduction
  • Crescenzi's survey places this reduction among several non-equivalent approximation-preserving notions and emphasizes that the preserved property must be named rather than inferred from the word ‘reduction.’

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