Showing 2021Show all
2 papers · 1 filter
math.OC2021
A Game Theoretic Approach to a Problem in Polymatroid Maximization
Lisa Hellerstein, Thomas Lidbetter
We consider the problem of maximizing the minimum (weighted) value of all components of a vector over a polymatroid. This is a special case of the lexicographically optimal base pr…
cs.DS2021
A Tight Bound for Stochastic Submodular Cover
Lisa Hellerstein, Devorah Kletenik, Srinivasan Parthasarathy
We show that the Adaptive Greedy algorithm of Golovin and Krause (2011) achieves an approximation bound of for Stochastic Submodular Cover: here is the "goal va…