Greedy differential approximations for MIN SET COVER

Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice

Bazgan, Cristina; Monnot, Jérôme; Paschos, Vangelis; Serrière, Fabrice (2005), Greedy differential approximations for MIN SET COVER, in Vojtas, Peter, SOFSEM'05 : Theory and Practice of Computer Science, Springer : Berlin Heidelberg, p. 62-71

Type

Communication / Conférence

Date

2005

Conference country

SLOVAKIA

Book title

SOFSEM'05 : Theory and Practice of Computer Science

Book author

Vojtas, Peter

Publisher

Springer

Published in

Berlin Heidelberg

ISBN

978-3-540-24302-1

Pages

62-71

Metadata

Show full item record

Author(s)

Bazgan, Cristina
Monnot, Jérôme

Paschos, Vangelis
Serrière, Fabrice

Abstract (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/Delta and above by , where Delta is the maximum set-cardinality in the min set cover-instance. Next, we study an approximation algorithm for min weighted set cover and provide a tight lower bound of 1/Delta.

Subjects / Keywords

Min Set Cover; differential approximation