On approximation scheme preserving reducibility and its applications

DOI10.1007/s002249910001zbMath0952.68066OpenAlexW2050896380MaRDI QIDQ1969434

Pierluigi Crescenzi, Luca Trevisan

Publication date: 7 June 2000

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s002249910001

zbMATH Keywords

polynomial-time approximation schemePTAS-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Analyzing the complexity of finding good neighborhood functions for local search algorithms ⋮ A survey on the structure of approximation classes ⋮ COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES ⋮ Structure of polynomial-time approximation ⋮ Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness ⋮ Completeness in approximation classes beyond APX ⋮ Inequity aversion pricing over social networks: approximation algorithms and hardness results ⋮ Order preserving reductions and polynomial improving paths

This page was built for publication: On approximation scheme preserving reducibility and its applications