Approximation algorithm for stochastic set cover problem

DOI10.1007/978-3-030-57602-8_4zbMath1482.68277OpenAlexW3047700137MaRDI QIDQ2039642

Yanyan Li

Publication date: 5 July 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_4

zbMATH Keywords

approximation algorithmprimal-dualstochastic set cover

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Approximation algorithms for stochastic combinatorial optimization problems
• Improved performance of the greedy algorithm for partial cover
• A unified approach to approximating partial covering problems
• On the hardness of approximating minimum vertex cover
• Approximation algorithms for combinatorial problems
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• Improved low-degree testing and its applications
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Efficient probabilistic checkable proofs and applications to approximation
• Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Prospect Theory: An Analysis of Decision under Risk
• Approximation algorithms for partial covering problems
• A primal-dual -approximation algorithm for the stochastic facility location problem with submodular penalties
• Reducibility among Combinatorial Problems
• Submodular Function Minimization under Covering Constraints

This page was built for publication: Approximation algorithm for stochastic set cover problem