Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
DOI10.1080/00207160410001688592zbMATH Open1093.68145OpenAlexW2068641268MaRDI QIDQ4831416FDOQ4831416
Authors: Tınaz Ekim, Vangelis Th. Paschos 
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
Recommendations
- On approximation problems related to the independent set and vertex cover problems
- On the differential approximation of MIN SET COVER
- Preserving approximation in the min-weighted set cover problem
- A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- On approximation of the submodular set cover problem
- On combinatorial approximation of covering 0-1 integer programs and partial set cover
- Approximating the dense set-cover problem
- SOFSEM 2005: Theory and Practice of Computer Science
- Approximation algorithm for partial set multicover versus full set multicover
Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Optimization, approximation, and complexity classes
- Structure preserving reductions among convex optimization problems
- 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
This page was built for publication: Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4831416)
