Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty

DOI10.1007/s10878-021-00753-xzbMath1504.90134OpenAlexW3185873601MaRDI QIDQ2084632

Yanyan Li

Publication date: 18 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00753-x

zbMATH Keywords

stochastic optimizationapproximation algorithmsset coverprimal-dualrent or buy

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

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
• Approximation algorithms for combinatorial problems
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• The General Steiner Tree-Star problem.
• Primal-dual algorithms for connected facility location problems
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• Improved low-degree testing and its applications
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Efficient probabilistic checkable proofs and applications to approximation
• An improved LP-based approximation for steiner tree
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for partial covering problems
• Reducibility among Combinatorial Problems
• A lower bound for parallel submodular minimization
• Provisioning a virtual private network
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem

This page was built for publication: Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty