On generalizations of partial scenario set cover

DOI10.1016/J.TCS.2025.115654MaRDI QIDQ6879026zbMATH OpenFDO

Authors Shai Michael Dimant, Sven O. Krumke

Publication date 5 January 2026

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

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmset coverpartial coversubmodular set cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3634550 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• A Greedy Heuristic for the Set-Covering Problem
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• A primal-dual algorithm for the minimum partial set multi-cover problem
• A threshold of ln n for approximating set cover
• Algorithms for covering multiple submodular constraints and applications
• An analysis of approximations for maximizing submodular set functions—I
• An analysis of the greedy algorithm for the submodular set covering problem
• An approximation algorithm for the partial covering 0-1 integer program
• Analytical approach to parallel repetition
• Approximability of sparse integer programs
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithm for the minimum interval partial multi-cover problem
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithms for covering/packing integer programs
• Approximation algorithms for partial covering problems
• Approximation algorithms for the partition vertex cover problem
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Covering Problems with Hard Capacities
• Everywhere-sparse spanners via dense subgraphs
• Few cuts meet many point sets
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• Improved performance of the greedy algorithm for partial cover
• Local ratio method on partial set multi-cover
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Network flows. Theory, algorithms, and applications.
• On approximating (sparse) covering integer programs
• On approximating partial scenario set cover
• On colorful vertex and edge cover problems
• On combinatorial approximation of covering 0-1 integer programs and partial set cover
• Partial resampling to approximate covering integer programs
• Primal-Dual Schema for Capacitated Covering Problems
• Robust multicovers with budgeted uncertainty
• Robust multicovers: algorithms and complexity
• Satisfiability to coverage in presence of fairness, matroid, and global constraints
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

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

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