• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
1997
Journal name
ACM Computing Surveys
Volume
29
Number
2
Publisher
ACM
Pages
171-209
Publication identifier
http://doi.acm.org/10.1145/254180.254190
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Abstract (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 algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    On the approximation of NP-complete problems by using Boltzmann machine method. The cases of some covering and packing problems 
    Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Communication / Conférence
  • Thumbnail
    On the approximation of NP-complete problems by using Boltzmann machine method: the cases of some covering and packing problems 
    Zissimopoulos, Vassilis; Paschos, Vangelis; Pekergin, Ferhan (1991) Article accepté pour publication ou publié
  • Thumbnail
    Approximating the optimal solutions of some hard graph problems by a Boltzmann machine 
    Paschos, Vangelis; Pekergin, Ferhan; Zissimopoulos, Vassilis (1993) Article accepté pour publication ou publié
  • Thumbnail
    Computing optimal solutions for the MIN 3-SET COVERING problem 
    Della Croce, Federico; Paschos, Vangelis (2005) Communication / Conférence
  • Thumbnail
    Approximation algorithms for minimum set covering problem: a survey 
    Paschos, Vangelis; Demange, Marc (1994) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo