Hardness of SetCover reoptimization

DOI10.1007/978-3-032-27732-9_26MaRDI QIDQ7363397zbMATH OpenFDO

Authors Klaus Jansen, Tobias Mömke, Björn Schumacher

Publication date 29 September 2026

Full work available at URL https://doi.org/10.1007/978-3-032-27732-9_26

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• A Tight Analysis of the Greedy Algorithm for Set Cover
• Algorithmic construction of sets for k -restrictions
• Analytical approach to parallel repetition
• Approximation algorithms for combinatorial problems
• Approximation and Online Algorithms
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Non-approximability results for optimization problems on bounded degree instances
• On the hardness of approximating minimization problems
• On the Hardness of Reoptimization
• On the ratio of optimal integral and fractional covers
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Reoptimization of set covering problems
• Reoptimization of Weighted Graph and Covering Problems
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

This page was built for publication: Hardness of SetCover reoptimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363397)