Structure in Approximation Classes
From MaRDI portal
Publication:4268816
DOI10.1137/S0097539796304220zbMath0932.68137MaRDI QIDQ4268816
Luca Trevisan, Viggo Kann, Pierluigi Crescenzi, Riccardo Silvestri
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
approximation algorithmscomplexity classesapproximation classesreducibilitiesAPX-intermediate problemsNPO-complete problems
Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (23)
A bilevel planning model for public-private partnership ⋮ Some Basic Techniques Allowing Petri Net Synthesis: Complexity and Algorithmic Issues ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ Genetic local search and hardness of approximation for the server load balancing problem ⋮ Differential approximation of MIN SAT, MAX SAT and related problems ⋮ On the Complexity of Wafer-to-Wafer Integration ⋮ A survey on the structure of approximation classes ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES ⋮ On the complexity of wafer-to-wafer integration ⋮ Structure of polynomial-time approximation ⋮ Reductions, completeness and the hardness of approximability ⋮ The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion ⋮ On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Completeness in approximation classes beyond APX ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Some APX-completeness results for cubic graphs ⋮ On the hardness of approximating the min-hack problem ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ On complexity of the bilevel location and pricing problems
This page was built for publication: Structure in Approximation Classes
