Structure in approximation classes

DOI10.1007/BFB0030875MaRDI QIDQ6085751zbMATH OpenOpenAlexFDO

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

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030875

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 709537 (Why is no real title available?)
• scientific article; zbMATH DE number 2077131 (Why is no real title available?)
• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• scientific article; zbMATH DE number 751135 (Why is no real title available?)
• Approximation algorithms for combinatorial problems
• Completeness in approximation classes
• On Bounded Queries and Approximation
• On Syntactic versus Computational Views of Approximability
• On the Structure of Polynomial Time Reducibility
• On the approximability of the maximum common subgraph problem
• On the complexity of approximating the independent set problem
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• The NP-Completeness of Edge-Coloring
• The approximation of maximum subgraph problems
• The complexity of 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 Q6085751)