Author name cluster

Devorah Kletenik

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

JAIR Journal 2021 Journal Article

A Tight Bound for Stochastic Submodular Cover

Lisa Hellerstein
Devorah Kletenik
Srinivasan Parthasarathy

We show that the Adaptive Greedy algorithm of Golovin and Krause achieves an approximation bound of (ln(Q/η)+1) for Stochastic Submodular Cover: here Q is the “goal value” and η is the minimum gap between Q and any attainable utility value Q' 2. A bound of 56(ln(Q/η)+1) is implied by work of Im et al. Other bounds for the problem depend on quantities other than Q and η. Our bound restores the original bound claimed by Golovin and Krause, generalizing the well-known (ln m + 1) approximation bound on the greedy algorithm for the classical Set Cover problem, where m is the size of the ground set.

PDF Details DOI

JAIR Journal 2018 Journal Article

Revisiting the Approximation Bound for Stochastic Submodular Cover

Lisa Hellerstein
Devorah Kletenik

Deshpande et al. presented a k(ln R + 1) approximation bound for Stochastic Submodular Cover, where k is the state set size, R is the maximum utility of a single item, and the utility function is integer-valued. This bound is similar to the ln Q/(eta+1) bound given by Golovin and Krause, whose analysis was recently found to have an error. Here Q >= R is the goal utility and eta is the minimum gap between Q and any attainable utility Q' < Q. We revisit the proof of the k(ln R + 1) bound of Deshpande et al., fill in the details of the proof of a key lemma, and prove two bounds for real-valued utility functions: k(ln R_1 + 1) and (ln R_E + 1). Here R_1 equals the maximum ratio between the largest increase in utility attainable from a single item, and the smallest non-zero increase attainable from that same item (in the same state). The quantity R_E equals the maximum ratio between the largest expected increase in utility from a single item, and the smallest non-zero expected increase in utility from that same item. Our bounds apply only to the stochastic setting with independent states.

PDF Details DOI

SODA Conference 2014 Conference Paper

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

Amol Deshpande
Lisa Hellerstein
Devorah Kletenik

We present approximation algorithms for two problems: Stochastic Boolean Function Evaluation (SBFE) and Stochastic Submodular Set Cover (SSSC). Our results for SBFE problems are obtained by reducing them to SSSC problems through the construction of appropriate utility functions. We give a new algorithm for the SSSC problem that we call Adaptive Dual Greedy. We use this algorithm to obtain a 3-approximation algorithm solving the SBFE problem for linear threshold formulas. We also get a 3-approximation algorithm for the closely related Stochastic Min-Knapsack problem, and a 2-approximation for a natural special case of that problem. In addition, we prove a new approximation bound for a previous algorithm for the SSSC problem, Adaptive Greedy. We consider an approach to approximating SBFE problems using existing techniques, which we call the Q -value approach. This approach easily yields a new result for evaluation of CDNF formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q -value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for linear threshold formulas or read-once DNF.

Details