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 algorithmsapproximation classesAPX-intermediate problemscomplexity classesNPO-complete problemsreducibilities

Mathematics Subject Classification ID

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

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

(37)

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