Structure in Approximation Classes

DOI10.1137/S0097539796304220MaRDI QIDQ4268816zbMATH OpenFDO

Authors Pilu Crescenzi, Viggo Kann, Luca Trevisan, Riccardo Silvestri

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539796304220

zbMATH Keywords

approximation algorithmscomplexity classesapproximation classesreducibilitiesAPX-intermediate problemsNPO-complete problems

Mathematics Subject Classification ID

Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Completeness in approximation classes
• scientific article; zbMATH DE number 17535
• scientific article; zbMATH DE number 847149
• A survey on the structure of approximation classes

Cited in

(36)

• Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues
• On the hardness of approximating the min-hack problem
• Nondeterministic functions and the existence of optimal proof systems
• A bilevel planning model for public-private partnership
• Identifying codes in hereditary classes of graphs and VC-dimension
• Approximating values and solutions of NP-optimization problems: concepts and examples
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
• scientific article; zbMATH DE number 2000419 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• Differential approximation of MIN SAT, MAX SAT and related problems
• On approximability of linear ordering and related NP-optimization problems on graphs.
• On the complexity of wafer-to-wafer integration
• Some APX-completeness results for cubic graphs
• On the complexity of wafer-to-wafer integration
• On complexity of the bilevel location and pricing problems
• Hop constrained Steiner trees with multiple root nodes
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• A survey on the structure of approximation classes
• Structural limits and approximations of mappings
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• A categorical view to structural complexity
• Weighted automata and logics meet computational complexity
• Genetic local search and hardness of approximation for the server load balancing problem
• The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion
• scientific article; zbMATH DE number 17535 (Why is no real title available?)
• Approximation properties of NP minimization classes
• On approximation scheme preserving reducibility and its applications
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• scientific article; zbMATH DE number 5263318 (Why is no real title available?)
• scientific article; zbMATH DE number 6490914 (Why is no real title available?)
• Structure of polynomial-time approximation
• Bounded queries, approximations, and the Boolean hierarchy
• Reductions, completeness and the hardness of approximability
• Completeness in approximation classes beyond APX
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Structural properties of bounded relations with an application to NP optimization problems

This page was built for publication: Structure in Approximation Classes

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