5 citations · 19 across the 13 of their papers we have counts for
15 papers
A Local Search Algorithm for the Min-Sum Submodular Cover Problem
Lisa Hellerstein, Thomas Lidbetter, R. Teal Witter
We consider the problem of solving the Min-Sum Submodular Cover problem using local search. The Min-Sum Submodular Cover problem generalizes the NP-complete Min-Sum Set Cover probl…
Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem
Lisa Hellerstein, Devorah Kletenik, Naifeng Liu +1
We consider the Stochastic Boolean Function Evaluation (SBFE) problem where the task is to efficiently evaluate a known Boolean function on an unknown bit string of length…
The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions
Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein +1
We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an -approximation al…
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…
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…
A General Framework for Approximating Min Sum Ordering Problems
Felix Happach, Lisa Hellerstein, Thomas Lidbetter
We consider a large family of problems in which an ordering (or, more precisely, a chain of subsets) of a finite set must be chosen to minimize some weighted sum of costs. This fam…