Approximation preserving reductions

MaRDI QIDQ3059319zbMATH OpenFDO

Authors Vangelis Th. Paschos, Giorgio Ausiello

Publication date 8 December 2010

zbMATH Keywords

ApproximabilityComplete problemComplexity hierarchyComputational complexityReduction

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Reductions, completeness and the hardness of approximability
• Completeness in approximation classes
• scientific article; zbMATH DE number 17535
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• On approximation scheme preserving reducibility and its applications

Cited in

(10)

• Continuous reductions among combinatorial optimization problems
• On approximation scheme preserving reducibility and its applications
• Reductions, completeness and the hardness of approximability
• Order preserving reductions and polynomial improving paths
• scientific article; zbMATH DE number 2079345 (Why is no real title available?)
• scientific article; zbMATH DE number 915981 (Why is no real title available?)
• Comparison of Some Reduced Representation Approximations
• Survey of polynomial transformations between NP-complete problems
• MNP: A class of NP optimization problems
• Fair interventions in weighted congestion games

This page was built for publication: Approximation preserving reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3059319)