Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems
From MaRDI portal
Publication:2956881
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
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