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

DOI10.1051/ita/2016022zbMath1400.68081arXiv1309.4718OpenAlexW2526148662MaRDI QIDQ2956881

Édouard Bonnet, Florian Sikora, Vangelis Th. Paschos

Publication date: 19 January 2017

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.4718

zbMATH Keywords

parameterized complexityparameterized approximationmax k-set cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Parameterised temporal exploration problems ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ Voting on multi-issue domains with conditionally lexicographic preferences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
• W-hierarchies defined by symmetric gates
• Parameterized approximation of dominating set problems
• Computing small partial coverings
• The Turing way to parameterized complexity
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Parameterized complexity of Vertex Cover variants
• Approximating low-dimensional coverage problems
• A threshold of ln n for approximating set cover
• The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• On Parameterized Approximability
• Parameterized Approximation Problems
• Set Partitioning via Inclusion-Exclusion
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
• Parameterized and Exact Computation

This page was built for publication: Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems