scientific article; zbMATH DE number 915981

zbMATH Open0859.68029MaRDI QIDQ4889464FDOQ4889464

Authors: Vangelis Th. Paschos, Laure Renotte 

Publication date: 28 October 1996

Title of this publication is not available (Why is that?)

Recommendations

• Reductions, completeness and the hardness of approximability
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• On Approximate Solutions for Combinatorial Optimization Problems
• Approximation preserving reductions
• scientific article; zbMATH DE number 847149

zbMATH Keywords

NP-complete problemsapproximability preserving reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (9)

• Continuous reductions among combinatorial optimization problems
• The Shrinking Property for NP and coNP
• The shrinking property for NP and coNP
• Reducing the number of solutions of NP functions
• A useful transform of standard input data for a classical NP-complete problem
• Automatic Evaluation of Reductions between NP-Complete Problems
• Title not available (Why is that?)
• Reductions, completeness and the hardness of approximability
• Nonuniform reductions and NP-completeness

This page was built for publication:

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