Metraipolis › archive › dc_8cbf4da4d8dc
Approximation-preserving reduction — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Approximation-preserving_reduction
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-09T17:39:02.963Z
- SHA-256 of the archived text
7528c396c2296db4146d2a4d793d5e13913687eedbf75931f0cd4bfd8ec76102- Stable URL of this page
https://metraipolis.com/documento/dc_8cbf4da4d8dc
How to cite
Approximation-preserving reduction — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Approximation-preserving_reduction (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8cbf4da4d8dc (Metraipolis archive dc_8cbf4da4d8dc, sha256 7528c396c2296db4146d2a4d793d5e13913687eedbf75931f0cd4bfd8ec76102)
BibTeX
@misc{dc8cbf4da4d8dc,
title = {Approximation-preserving reduction — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Approximation-preserving_reduction},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8cbf4da4d8dc; sha256 7528c396c2296db4146d2a4d793d5e13913687eedbf75931f0cd4bfd8ec76102},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Approximation-preserving_reduction. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are special cases of the general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems. Intuitively, problem A is reducible to problem B via an approximation-preserving reduction if, given an instance of problem A and a (possibly approximate) solver for problem B, one can convert the instance of problem A into an instance of problem B, apply the solver for problem B, and recover a solution for problem A that also has some guarantee of approximation. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in inglese, in ordine alfabetico). Fonte: Wikipedia in inglese, voce «Approximation-preserving reduction» — https://en.wikipedia.org/wiki/Approximation-preserving_reduction Wikidata Q25303750: «algorithm for transforming one optimization problem into another» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q25303750 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Approximation-preserving_reduction?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1357847632, consultata il 2026-11-09T17:35:35.679Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: fb03db3d1fec094a2fff4bfa39f80370dd394fdd1a8dd3e63f7fc32f4cb12d98