Optimization, Approximation, and Complexity Classes¶
Papadimitriou, C. H., & Yannakakis, M. (1991). Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences, 0000(91), 425-440.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
- L-Reduction
- Papadimitriou and Yannakakis introduced the construction while developing the classes MAX NP and MAX SNP; its purpose was to make completeness and hardness results preserve approximability rather than mere yes/no solvability.
This sourceIntroduces MAX NP/MAX SNP and L-reductions as approximation-preserving transformations.
- Papadimitriou and Yannakakis introduced the construction while developing the classes MAX NP and MAX SNP; its purpose was to make completeness and hardness results preserve approximability rather than mere yes/no solvability.
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:92a4f1d15b72 · see in the full table