Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
From MaRDI portal
Publication:4831416
DOI10.1080/00207160410001688592zbMath1093.68145OpenAlexW2068641268MaRDI QIDQ4831416
Vangelis Th. Paschos, Tınaz Ekim
Publication date: 29 December 2004
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207160410001688592
Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- On Approximate Solutions for Combinatorial Optimization Problems