A survey of approximately optimal solutions to some covering and packing problems
Paschos, Vangelis (1997), A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys, 29, 2, p. 171-209. http://doi.acm.org/10.1145/254180.254190
Type
Article accepté pour publication ou publiéDate
1997Journal name
ACM Computing SurveysVolume
29Number
2Publisher
ACM
Pages
171-209
Publication identifier
Metadata
Show full item recordAuthor(s)
Paschos, VangelisAbstract (EN)
We survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex covering, the maximum set packing, and maximum independent set problems; we discuss their approximation performance and their complexity. For already known results, any time we have conceived simpler proofs than those already published, we give these proofs, and, for the rest, we cite the simpler published ones. Finally, we discuss how one can relate the approximability behavior (from both a positive and a negative point of view) of vertex covering to the approximability behavior of a restricted class of independent set problems.Subjects / Keywords
Combinatorial optimization; Approximation algorithmsRelated items
Showing items related by title and author.
-
Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Communication / Conférence
-
Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Article accepté pour publication ou publié
-
Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1993) Article accepté pour publication ou publié
-
Della Croce, Federico; Paschos, Vangelis (2005) Communication / Conférence
-
Paschos, Vangelis; Demange, Marc (1994) Article accepté pour publication ou publié