• 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 - No thumbnail

Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems

Bonnet, Édouard; Paschos, Vangelis; Sikora, Florian (2016), Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems, RAIRO - Theoretical Informatics and Applications, 50, 3, p. 227-240. 10.1051/ita/2016022

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1309.4718v3
Date
2016
Journal name
RAIRO - Theoretical Informatics and Applications
Volume
50
Number
3
Pages
227-240
Publication identifier
10.1051/ita/2016022
Metadata
Show full item record
Author(s)
Bonnet, Édouard cc
Institute for Computer Science and Control [Budapest] [SZTAKI]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Given a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamily T ⊆ S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.
Subjects / Keywords
Parameterized complexity; parameterized approximation; max k-set cover
JEL
C69 - Other

Related items

Showing items related by title and author.

  • Thumbnail
    Purely combinatorial approximation algorithms for maximum k -vertex cover in bipartite graphs 
    Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Georgios (2018) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Thumbnail
    A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs 
    Bonnet, Edouard; Escoffier, Bruno; Paschos, Vangelis; Stamoulis, Giorgios (2016) Communication / Conférence
  • Thumbnail
    EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs 
    Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié
  • Thumbnail
    QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs 
    Bonnet, Édouard; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, Pawel; Sikora, Florian (2018) Communication / Conférence
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