A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem

DOI10.4230/LIPIcs.ICALP.2019.81OpenAlexW2964642894MaRDI QIDQ5091240

Bingkai Lin

Publication date: 21 July 2022

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

zbMATH Keywords

set cover\((n,k)\)-universal setFPT inapproximabilitygap-producing reduction

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

On the parameterized complexity of compact set packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of fixed parameter clique and dominating set
• Exponential-time approximation of weighted set cover
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Which problems have strongly exponential complexity?
• Two combinatorial covering theorems
• The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
• Parametrized complexity theory.
• Losing Weight by Gaining Edges
• Algorithmic construction of sets for k -restrictions
• Extremal Combinatorics
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• A Tight Analysis of the Greedy Algorithm for Set Cover
• The Parameterized Complexity of the k -Biclique Problem
• Reducibility among Combinatorial Problems
• On the parameterized complexity of approximating dominating set
• Analytical approach to parallel repetition
• Exact Weight Subgraphs and the k-Sum Conjecture
• The Parameterized Complexity of k-B<scp>iclique</scp>
• On the complexity of \(k\)-SAT

This page was built for publication: A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem