Completeness in Approximation Classes

Crescenzi, P., & Panconesi, A. (1991). Completeness in Approximation Classes. Information and Computation, 5401(91), 241-262.

Type

Journal article

Intellectual base

Primary research

Year

1991

DOI

10.1016/0890-5401(91)90025-w

Link

https://doi.org/10.1016/0890-5401(91)90025-W

Cited by

1 citation across 1 artifact.

Domain-specific

• PTAS Reduction
  • Crescenzi and Panconesi introduced systematic approximation-class reductions to support completeness results for NPO, APX, and PTAS rather than treating exact many-one reductions as sufficient.

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