
On the differential approximation of MIN SET COVER
Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005), On the differential approximation of MIN SET COVER, Theoretical Computer Science, 332, 1-3, p. 497-513. http://dx.doi.org/10.1016/j.tcs.2004.12.022
View/ Open
Type
Article accepté pour publication ou publiéDate
2005Journal name
Theoretical Computer ScienceVolume
332Number
1-3Publisher
Elsevier
Pages
497-513
Publication identifier
Metadata
Show full item recordAbstract (EN)
We present in this paper differential approximation results for MIN SET COVER and MIN WEIGHTED SET COVER. We first show that the differential approximation ratio of the natural greedy algorithm for MIN SET COVER is bounded below by 1.365/Δ and above by 4/(Δ+1), where Δ is the maximum set-cardinality in the MIN SET COVER-instance. Next, we study another approximation algorithm for MIN SET COVER that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. We prove that the differential approximation ratio of this second algorithm is bounded below by 2/(Δ+1) and that this bound is tight. Finally, we study an approximation algorithm for MIN WEIGHTED SET COVER and provide a tight lower bound of 1/Δ. Our results identically hold for MAX HYPERGRAPH INDEPENDENT SET in both the standard and the differential approximation paradigms.Subjects / Keywords
Complexity; Approximation algorithms; Greedy algorithm; Set cover; Combinatorial problemRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005) Communication / Conférence
-
Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, F. (2005) Article accepté pour publication ou publié
-
Bazgan, Cristina; Brankovic, Ljiljana; Casel, Katrin; Fernau, Henning; Jansen, Klaus; Klein, Kim-Manuel; Lampis, Michael; Liedloff, Mathieu; Monnot, Jérôme; Paschos, Vangelis (2018) Article accepté pour publication ou publié
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié