On approximating partial scenario set cover

DOI10.1016/J.TCS.2024.114891MaRDI QIDQ6652422zbMATH OpenFDO

Authors Shai Michael Dimant, Sven O. Krumke

Publication date 12 December 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114891

zbMATH Keywords

approximation algorithmcombinatorial optimizationNP-hardnesspartial coverset cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithms for partial covering problems
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Parallel approximation for partial set cover
• scientific article; zbMATH DE number 1754596

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Algorithms for covering multiple submodular constraints and applications
• Analytical approach to parallel repetition
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithms for partial covering problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Combinatorial Optimization with Rational Objective Functions
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 1256706 (Why is no real title available?)
• Improved performance of the greedy algorithm for partial cover
• On Finding Dense Subgraphs
• On partial covering for geometric set systems
• Optimization, approximation, and complexity classes
• Robust multicovers with budgeted uncertainty
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The densest k-subhypergraph problem
• The design of approximation algorithms
• Using homogeneous weights for approximating the partial cover problem
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(1)

• On generalizations of partial scenario set cover

This page was built for publication: On approximating partial scenario set cover

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