On approximating partial scenario set cover

DOI10.1016/j.tcs.2024.114891MaRDI QIDQ6652422

Shai Michael Dimant, Sven O. Krumke

Publication date: 12 December 2024

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmNP-hardnessset coverpartial cover

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• Optimization, approximation, and complexity classes
• Robust multicovers with budgeted uncertainty
• Approximation algorithm for the partial set multi-cover problem
• Algorithms for covering multiple submodular constraints and applications
• Using homogeneous weights for approximating the partial cover problem
• The Design of Approximation Algorithms
• A threshold of ln n for approximating set cover
• The Densest $k$-Subhypergraph Problem
• Set connectivity problems in undirected graphs and the directed steiner network problem
• On Finding Dense Subgraphs
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Approximation algorithms for partial covering problems
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• On Partial Covering For Geometric Set Systems
• Analytical approach to parallel repetition

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