Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
From MaRDI portal
Publication:4831416
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
Cites work
- Differential approximation algorithms for some combinatorial optimization problems
- On Approximate Solutions for Combinatorial Optimization Problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Optimization, approximation, and complexity classes
- Structure preserving reductions among convex 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)
