The submodularity of two-stage stochastic maximum-weight independent set problems
From MaRDI portal
Publication:2089673
DOI10.1016/j.tcs.2022.09.029OpenAlexW4297498073MaRDI QIDQ2089673
Min Li, Hao Xiao, Qian Liu, Yang Zhou
Publication date: 24 October 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.09.029
Cites Work
- Unnamed Item
- Sell or hold: A simple two-stage stochastic combinatorial optimization problem
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Robust monotone submodular function maximization
- Parametric monotone function maximization with matroid constraints
- Two-stage stochastic max-weight independent set problems
- Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- Computational complexity of stochastic programming problems
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Theory and Applications of Robust Optimization
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- On the random 2-stage minimum spanning tree
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
- An analysis of approximations for maximizing submodular set functions—I
- Deterministic Algorithms for Submodular Maximization Problems
- Parallelizing greedy for submodular set function maximization in matroids and beyond
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Matroids and the greedy algorithm
This page was built for publication: The submodularity of two-stage stochastic maximum-weight independent set problems
