On the differential approximation of MIN SET COVER

DOI10.1016/j.tcs.2004.12.022zbMath1070.68153OpenAlexW2092740206MaRDI QIDQ1770405

Fabrice Serriére, Cristina Bazgan, Vangelis Th. Paschos, Jérôme Monnot

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.12.022

zbMATH Keywords

ComplexityApproximation algorithmsGreedy algorithmSet coverCombinatorial problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (6)

Equivalent characterizations of some graph problems by covering-based rough sets ⋮ A survey on the structure of approximation classes ⋮ A better differential approximation ratio for symmetric TSP ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ Independent sets in bounded-degree hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure preserving reductions among convex optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Differential approximation algorithms for some combinatorial optimization problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Improved approximations for maximum independent set via approximation chains
• The maximum saving partition problem
• z-Approximations
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• Approximations of Weighted Independent Set and Hereditary Subset Problems

This page was built for publication: On the differential approximation of MIN SET COVER