Scenario Submodular Cover
Nathaniel Grammel∗

ngrammel@nyu.edu

Department of Computer Science and Engineering
NYU Tandon School of Engineering
Brooklyn, NY 11201

arXiv:1603.03158v1 [] 10 Mar 2016

Lisa Hellerstein∗

lisa.hellerstein@nyu.edu

Department of Computer Science and Engineering
NYU Tandon School of Engineering
Brooklyn, NY 11201

Devorah Kletenik∗

kletenik@sci.brooklyn.cuny.edu

Department of Computer and Information Science
Brooklyn College, City University of New York
2900 Bedford Avenue
Brooklyn, NY 11210

Patrick Lin∗

plin15@illinois.edu

Department of Computer Science
University of Illinois at Urbana-Champaign
Urbana, IL

Abstract
Many problems in Machine Learning can be modeled as submodular optimization problems.
Recent work has focused on stochastic or adaptive versions of these problems. We consider
the Scenario Submodular Cover problem, which is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause (2011). In Scenario Submodular Cover,
the goal is to produce a cover with minimum expected cost, where the expectation is with
respect to an empirical joint distribution, given as input by a weighted sample of realizations. In contrast, in Stochastic Submodular Cover, the variables of the input distribution
are assumed to be independent, and the distribution of each variable is given as input.
Building on algorithms developed by Cicalese et al. (2014) and Golovin and Krause (2011)
for related problems, we give two approximation algorithms for Scenario Submodular Cover
over discrete distributions. The first achieves an approximation factor of O(log Qm), where
m is the size of the sample and Q is the goal utility. The second, simpler algorithm achieves
an approximation bound of O(log QW ), where Q is the goal utility and W is the sum of the
integer weights. (Both bounds assume an integer-valued utility function.) Our results yield
approximation bounds for other problems involving non-independent distributions that are
explicitly specified by their support.
∗

Partially Supported by NSF Grant 1217968

c 2016 N. Grammel, L. Hellerstein, D. Kletenik & P. Lin.

Grammel Hellerstein Kletenik Lin

1. Introduction
Many problems in Machine Learning can be modeled as submodular optimization problems.
Recent work has focused on stochastic or adaptive versions of submodular optimization
problems, which reflect the need to make sequential decisions when outcomes are uncertain.
The Submodular Cover problem generalizes the classical NP-complete Set Cover problem and is a fundamental problem in submodular optimization. Adaptive versions of this
problem have applications to a variety of machine learning problems that require building a
decision tree, where the goal is to minimize expected cost. Examples include problems of entity identification (exact learning with membership queries), classification (equivalence class
determination), and decision region identification (cf. Golovin and Krause (2011); Golovin
et al. (2010); Bellala et al. (2012); Javdani et al. (2014)). Other applications include reducing prediction costs for learned Boolean classifiers, when there are costs for determining
attribute values (Deshpande et al. (2014)).
Previous work on the Stochastic Submodular Cover problem assumes that the variables
of the input probability distribution are independent. Optimization is performed with respect to this distribution. We consider a new version of the problem that we call Scenario
Submodular Cover, that removes the independence assumption. In this problem, optimization is performed with respect to an input distribution that is given explicitly by its
support (with associated probability weights). We give approximation algorithms solving
the Scenario Submodular Cover problem over discrete distributions.
Before describing our contributions in more detail, we give some background. In generic
terms, an adaptive submodular cover problem is a sequential decision problem where we
must choose items one by one from an item set N = {1, . . . , n}. Each item has an initially
unknown state, which is a member of a finite state set Γ. The state of an item is revealed
only after we have chosen the item. We represent a subset S of items and their states by
a vector x ∈ (Γ ∪ {∗})n where xi = ∗ if i 6∈ S, and xi is the state of item i otherwise.
We are given a monotone, submodular utility function g : (Γ ∪ {∗})n → Z≥0 . It assigns
a non-negative integer value to each subset of the items and the value can depend on the
states of the items.1 There is a non-negative goal utility value Q, such that g(a) = Q for
all a ∈ Γn . There is a cost associated with choosing each item, which we are given. In
distributional settings, we are also given the joint distribution of the item states. We must
continue choosing items until their utility value is equal to the goal utility, Q. The problem
is to determine the adaptive order in which to choose the items so as to minimize expected
cost (in distributional settings) or worst-case cost (in adversarial settings).
Stochastic Submodular Cover is an adaptive submodular cover problem, in a distributional setting. In this problem, the state of each item is a random variable, and these variables are assumed to be independent. The distributions of the variables are given as input.
Golovin and Krause introduced a simple greedy algorithm for this problem, called Adaptive
Greedy, that achieves an approximation factor of O(log Q). A dual greedy algorithm for
the problem, called Adaptive Dual Greedy, was presented and analyzed by Deshpande et al.
(2014). These greedy algorithms have been useful in solving other stochastic optimization
1. The definitions of the terms “monotone” and “submodular,” for state-dependent utility functions, has
not been standardized. We define these terms in Section 2. In the terminology used by Golovin and
Krause Golovin and Krause (2011), g is pointwise monotone and pointwise submodular.

2

Scenario Submodular Cover

problems, which can be reduced to Stochastic Submodular Cover through the construction
of appropriate utility functions (e.g., Javdani et al. (2014); Chen et al. (2015a); Deshpande
et al. (2014); Golovin et al. (2010)).
The problem we study in this paper, Scenario Submodular Cover (Scenario SC), is also a
distributional, adaptive submodular cover problem. The distribution is given by a weighted
sample, which is provided as part of the input to the problem. Each element of the sample
is a vector in Γn , representing an assignment of states to the items in N . Associated with
each assignment is a positive integer weight. The sample and its weights define a joint
distribution on Γn , where the probability of a vector γ in the sample is proportional to its
weight. (The probability of a vector in Γn that is not in the sample is 0.) As in Stochastic
Submodular Cover, the problem is to choose the items and achieve utility Q, in a way that
minimizes the expected cost incurred. However, because many of the proofs of results for
the Stochastic Submodular Cover problem rely on the independence assumption, the proofs
do not apply to the Scenario SC problem.
Results
We present an approximation algorithm for the Scenario SC problem that we call Mixed
Greedy. It uses two different greedy criteria. It is a generalization of an algorithm by Cicalese
et al. (2014) for the Equivalence Class Determination problem (which has also been called
the Group Identification problem and the Discrete Function Evaluation problem).
factor achieved by Mixed Greedy for the Scenario SC problem is
The approximation

1
O ρ log Q , where ρ is a quantity that depends on the utility function g. In the case of the
utility function constructed for the Equivalence Class Determination Problem, ρ is constant,
but this is not true in general.
We describe a modified version of Mixed Greedy that we call Scenario Mixed Greedy.
It works by first constructing a new monotone, submodular utility function gS from g and
the sample, for which ρ is constant. It then runs Mixed Greedy on gS with goal value
Qm, where m is the size of the sample. We show that Scenario Mixed Greedy achieves an
O(log Qm) approximation factor for any Scenario SC problem.
Mixed Greedy is very similar to the algorithm of Cicalese et al., and we use the same basic
analysis. However, at the heart of their analysis is a technical lemma with a lengthy proof
bounding a quantity that they call the “sepcost”. The proof applies only to the particular
utility function used in the Equivalence Class Determination problem. We replace this proof
with an entirely different proof that applies to the general Scenario SC problem. Our proof
is based on the work of Streeter and Golovin (2009) for the Min-Sum Submodular Cover
problem.
In addition to presenting and analyzing Mixed Greedy, we also present another algorithm
for the Scenario SC problem that we call Scenario Adaptive Greedy. It is a modified version
of the Adaptive Greedy algorithm of Golovin and Krause. Scenario Adaptive Greedy is
simpler and more efficient than Mixed Greedy, and is therefore likely to be more useful in
practice. However, the approximation bound proved by Golovin and Krause for Adaptive
Greedy depends on the assumption that g and the distribution defined by the sample
weights jointly satisfy the adaptive submodularity property. This is not the case for general
instances of the Scenario SC problem. We extend the approach used in constructing gS to

3

Grammel Hellerstein Kletenik Lin

give a simple, generic method for constructing a modified utility function gW , with goal
utility QW , from g, which incorporates the weights on the sample. We prove that utility
function gW and the distribution defined by the sample weights jointly satisfy adaptive
submodularity. This allows us to apply the Adaptive Greedy algorithm, and to achieve an
approximation bound of O(log QW ) for the Scenario SC problem, where W is the sum of
the weights.
Our constructions of gS and gW are similar to constructions used in previous work on
Equivalence Class Determination and related problems (cf. Golovin et al. (2010); Bellala
et al. (2012); Chen et al. (2015a,b)). Our proof of adaptive submodularity uses the same basic approach as used in previous work (see, e.g., Golovin et al. (2010); Chen et al. (2015a,b)),
namely showing that the value of a certain function is non-decreasing along a path between
two points; however, we are addressing a more general problem and the details of our proof
are different.
We believe that our work on Adaptive Greedy should make it easier to develop efficient approximation algorithms for sample-based problems in the future. Previously, using
ordinary Adaptive Greedy to solve a sample-based problem involved the construction of
a utility function g, and a proof that g, together with the distribution on the weighted
sample, was adaptive submodular. The proof was usually the most technically difficult part
of the work (see, e.g., Golovin et al. (2010); Bellala et al. (2012); Javdani et al. (2014);
Chen et al. (2015b)). Our construction of gW , and our proof of adaptive submodularity,
make it possible to achieve an approximation bound using Adaptive Greedy after proving
only submodularity of a constructed g, rather than adaptive submodularity of g and the
distribution. Proofs of submodularity are generally easier because they do not involve distributions and expected values. Also, the standard OR construction described in Section 2
preserves submodularity, while it does not preserve Adaptive Submodularity (Chen et al.
(2015a)).
Given a monotone, submodular g with goal value Q, we can use the algorithms in this paper to immediately obtain three approximation results
forthe associated Scenario SC prob
1
lem: running Mixed Greedy with g yields an O ρ log Q approximation, running Mixed
Greedy with gS yields an O(log Qm) approximation, and running Adaptive Greedy with gW
yields an O(log QW ) approximation. By the results of Golovin and Krause (2011), running
Adaptive Greedy with g yields an O(log Q) approximation for the associated Stochastic SC
problem.
Applications
Our results on Mixed Greedy yield approximation bounds for other problems. For example,
we can easily obtain a new bound for the Decision Region Identification problem studied
by Javdani et al. (2014), which is an extension of the Equivalence Class Determination problem. Javdani et al. construct a utility function whose value corresponds to a weighted sum
of the hyperedges cut in a certain hypergraph. We can define a corresponding utility function whose value is the number of hyperedges cut. This utility function is clearly monotone
and submodular. Using Mixed Greedy with this utility function yields an approximation
bound of O(k log m), where k is a parameter associated with the problem, and m is the size

4

Scenario Submodular Cover

of the input
 sample
 for this problem. In contrast, the bound achieved by Javdani et al. is
W
O k log wmin , where wmin is the minimum weight on a assignment in the sample.
We can apply our greedy algorithms to Scenario BFE (Boolean Function Evaluation)
problems, which we introduce here. These problems are a counterpart to the Stochastic
BFE problems2 that have been studied in AI, operations research, and in the context of
learning with attribute costs (see e.g., Ünlüyurt (2004); Deshpande et al. (2014); Kaplan
et al. (2005)). In a Scenario BFE problem, we are given a Boolean function f . For each
i ∈ {1, . . . , n}, we are also given a cost ci > 0 associated with obtaining the value of the ith
bit of an initially unknown assignment a ∈ {0, 1}n . Finally, we are given a weighted sample
S ⊆ {0, 1}n . The problem is to compute a (possibly implicit) decision tree computing f ,
such that the expected cost of evaluating f on a ∈ {0, 1}n , using the tree, is minimized.
The expectation is with respect to the distribution defined by the sample weights.
Deshpande et al. (2014) gave approximation algorithms for some Stochastic BFE problems that work by constructing an appropriate monotone, submodular utility function g
and running Adaptive Greedy. By substituting the sample-based algorithms in this paper
in place of Adaptive Greedy, we obtain approximation results for analogous Scenario BFE
problems. For example, using Mixed Greedy, we can show that the Scenario BFE problem
for k-of-n functions has an approximation algorithm achieving a factor of O(k log n) approximation, independent of the size of the sample. Details are in Appendix B. Bounds for other
functions follow easily using Scenario Mixed Greedy and Scenario Adaptive Greedy. For example, Deshpande et al. (2014) presented an algorithm achieving an O(log t) approximation
for the Stochastic BFE problem for evaluating decision trees of size t. Substituting Scenario
Mixed Greedy for Adaptive Greedy in this algorithm yields an O(log tm) approximation for
the associated Scenario BFE problem.
We note that our Scenario BFE problem differs from the function evaluation problem
by Cicalese et al. (2014). In their problem, the computed decision tree need only compute
f correctly on assignments a ∈ {0, 1}n that are in the sample, while ours needs to compute
f correctly on all a ∈ {0, 1}n . To see the difference, consider the problem of evaluating the
Boolean OR function, for a sample S consisting of only a ∈ {0, 1}n with at least one 1. If
the tree only has to be correct on a ∈ S, a one-node decision tree that immediately outputs
1 is valid, even though it does not compute the OR function. Also, in Scenario BFE we
assume that the function f is given with the sample, and we consider particular types of
functions f .
Organization
We begin with definitions in Section 2. In Section 3, we present the overview of the Mixed
Greedy algorithm. Finally, we present Scenario Mixed Greedy in Section 4, followed by
Scenario Adaptive Greedy in Section 5.
2. In the Operations Research literature, Stochastic Function Evaluation is often called Sequential Testing
or Sequential Diagnosis.

5

Grammel Hellerstein Kletenik Lin

2. Definitions
Let N = {1, . . . , n} be the set of items and Γ be a finite set of states. A sample is a subset
of Γn . A realization of the items is an element a ∈ Γn , representing an assignment of states
to items, where for i ∈ N , ai represents the state of item i. We also refer to an element of
Γn as an assignment.
We call b ∈ (Γ ∪ {∗})n a partial realization. Partial realization b represents the subset
of items I = {i | bi 6= ∗} where each item i ∈ I has state bi . For γ ∈ Γ, the quantity
bi←γ denotes the partial realization that is identical to b except that bi = γ. For partial
realizations b, b0 ∈ (Γ ∪ {∗})n , b0 is an extension of b, written b0  b, if b0i = bi for all bi 6= ∗.
We use b0  b to denote that b0  b and b0 6= b.
Let g : (Γ ∪ {∗})n → Z≥0 be a utility function. Utility function g : (Γ ∪ {∗})n → Z≥0
has goal value Q if g(a) = Q for all realizations a ∈ Γn .
We define ∆g(b, i, γ) := g(bi←γ ) − g(b).
A standard utility function is a set function f : 2N → R≥0 . It is monotone if for all
S ⊂ S 0 ⊆ N , f (S) ≤ f (S 0 ). It is submodular if in addition, for i ∈ N −S, f (S ∪{i})−f (S) ≥
f (S 0 ∪ {i}) − f (S 0 ). We extend the definitions of monotonicity and submodularity to (statedependent) utility function g : (Γ ∪ {∗})n → Z≥0 as follows:
• g is monotone if for b ∈ (Γ ∪ {∗})n , i ∈ N such that bi = ∗, and γ ∈ Γ, we have
g(b) ≤ g(bi←γ )
• g is submodular if for all b, b0 ∈ (Γ ∪ {∗})n such that b0  b, i ∈ N such that bi = b0i = ∗,
and γ ∈ Γ, we have ∆g(b, i, γ) ≥ ∆g(b0 i, γ).
Let D be a probability distribution on Γn . Let X be a random variable drawn from D.
For a ∈ Γn and b ∈ (Γ ∪ {∗})n , we
Pdefine Pr[a | b] := Pr[X = a | a  b]. For i such that
bi = ∗, we define E[∆g(b, i, γ)] := a∈Γn :ab ∆g(b, i, ai ) Pr[a | b].
• g is adaptive submodular with respect to D if for all b0 , b such that b0  b, i ∈ N such
that bi = b0i = ∗, and γ ∈ Γ, we have E[∆g(b, i, γ)] ≥ E[∆g(b0 , i, γ)].
Intuitively, we can view b as partial information about states of items i in a random
realization a ∈ Γn , with bi = ∗ meaning the state of item i is unknown. Then g measures
the utility of that information, and E[∆g (b, i, γ)] is the expected increase in utility that
would result from discovering the state of i.
For g : (Γ ∪ {∗})n → Z≥0 with goal value Q, and b ∈ (Γ ∪ {∗})n and i ∈ N , where bi = ∗,
let γb,i be the state γ ∈ Γ such that ∆g(b, i, γ) is minimized (if more than one minimizing
state exists, choose one arbitrarily). Thus γb,i is the state of item i that would produce the
smallest increase in utility, and thus is “worst-case” in terms of utility gain, if we start from
b and then discover the state of i.
For fixed g : (Γ ∪ {∗})n → Z≥0 with goal value Q, we define an associated quantity ρ, as
follows:
∆g(b, i, γ)
ρ := min
Q − g(b)
where the minimization is over b, i, γ, where b ∈ (Γ ∪ {∗})n such that g(b) < Q, i ∈ N ,
bi = ∗, and γ ∈ Γ − {γb,i }.
6

Scenario Submodular Cover

Intuitively, right before the state of an item i is discovered, there is a certain distance
from the current utility achieved to the goal utility. When the state of that item is discovered, the distance to goal is reduced by some fraction (or possibly by zero). The size of
that fraction can vary depending on the state of the item. In the definition of ρ, we are
concerned with the value of that fraction, not for the worst-case state in this case (leading to
the smallest fraction), but for the next-to-worst case state. The parameter ρ is the smallest
possible value for this fraction, starting from any partial realization, and considering any
item i whose state is about to be discovered.
An instance of the Scenario SC problem is a tuple (g, Q, S, w, c), where g : (Γ ∪ {∗})n →
Z≥0 is an integer-valued, monotone submodular utility function with goal value Q > 0,
S ⊆ Γn , w : S → Zn>0 assigns a weight to each realization a ∈ S, and c ∈ Rn>0 is a cost
vector. We consider a setting where we select items without repetition from the set of items
N , and the states of the items correspond to an initially unknown realization a ∈ Γn . Each
time we select an item, the state ai of the item is revealed. The selection of items can be
adaptive, in that the next item chosen can depend on the states of the previous items. We
continue to choose items until g(b) = Q, where b is the partial realization representing the
states of the chosen items.
The Scenario SC problem asks for an adaptive order in which to choose the items (i.e.,
a strategy), until goal value Q is achieved, such that the expected sum of the costs of the
chosen items is minimized. The expectation is with respect to the distribution on Γn that
is proportional to the weights on the assignments in the sample: Pr[a] = 0 if a 6∈ S, and
P
Pr[a] = w(a)
a∈S w(a). We call this the sample distribution defined
W otherwise, where W =
by S and w and denote it by DS,w .
The strategy corresponds to a decision tree. The internal nodes of the tree are labeled
with items i ∈ N , and each such node has one child for each state γ ∈ Γ. Each root-leaf
path in the tree is associated with a partial realization b such that for each consecutive pairs
of nodes v and v 0 on the path, if i is the label of v, and v 0 is the γ-child of v, then bi = γ. If
i does not label any node in the path, then bi = ∗. The tree may be output in an implicit
form (for example, in terms of a greedy rule), specifyng how to determine the next item to
choose, given the previous items chosen and their states. Although realizations a 6∈ S do
not contribute to the expected cost of the strategy, we require the strategy to achieve goal
value Q on all realizations a ∈ Γn .
We will make frequent use of a construction that we call the standard OR construction
(cf. Guillory and Bilmes (2011); Deshpande et al. (2014)). It is a method for combining two
monotone submodular utility functions g1 and g2 defined on (Γ ∪ {∗})n , and values Q1 and
Q2 , into a new monotone submodular utility function g. For b ∈ (Γ ∪ {∗})n ,
g(b) = Q1 Q2 − (Q1 − g1 (b))(Q2 − g2 (b))
Suppose that on any a ∈ Γn , g1 (a) = Q1 or g2 (a) = Q2 . Then, g(a) = Q1 Q2 for all a ∈ Γn .

3. Mixed Greedy
The Mixed Greedy algorithm is a generalization of the approximation algorithm developed
by Cicalese et al. for the Equivalence Class Determination problem. That algorithm effectively solves the Scenario Submodular Cover problem for a particular “Pairs” utility
7

Grammel Hellerstein Kletenik Lin

function associated with Equivalence Class Determination. In contrast, Mixed Greedy can
be used on any monotone, submodular utility function g.
Following Cicalese et al., we present Mixed Greedy as outputting a decision tree. If the
strategy is only to be used on one realization, it is not necessary to build the entire tree.
While Mixed Greedy is very similar to the algorithm of Cicalese et al, we describe it fully
here so that our presentation is self-contained.
3.1. Algorithm
The Mixed Greedy algorithm builds a decision tree for Scenario SC instance (g, Q, S, w, c).
The tree is built top-down. It has approximately optimal expected cost, with respect to the
sample distribution DS,w defined by S and w. Each internal node of the constructed tree
has |Γ| children, one corresponding to each state γ ∈ Γ. We refer to the child corresponding
to γ as the γ-child.
The Mixed Greedy algorithm works by calling the recursive function MixedGreedy,
whose pseudocode we present in Algorithm 1. In the initial call to MixedGreedy, b is set
to be equal to (∗, . . . , ∗). Only the value of b changes between the recursive calls; the other
values remain fixed. Each call to MixedGreedy constructs a subtree of the full tree for g,
rooted at a node v of that tree. In the recursive call that builds the subtree rooted at v, b is
the partial realization corresponding to the path from the root to v in the full tree: bi = γ
if the path includes a node labeled i and its γ-child, and bi = ∗ otherwise.
The algorithm of Cicalese et al. for the Equivalence Class Determination problem is
essentially the same as our Mixed Greedy algorithm, for g equal to their “Pairs” utility
function. (There is one small difference – in their algorithm, the first stage ends right
before the greedy step in which the budget B would be exceeded, whereas we allow the
budget to be exceeded in the last step.) Like their algorithm, our Mixed Greedy algorithm
relies on a greedy algorithm for the Budgeted Submodular Cover problem due to Wolsey.
We describe Wolsey’s algorithm in detail in Appendix A.1.
If g(b) = Q, then MixedGreedy returns an (unlabeled) single node, which will be a leaf
of the full tree for g. Otherwise, MixedGreedy constructs a tree T . It does so by computing
a special realization called σ, and then iteratively using σ to construct a path descending
from the root of this subtree, which is called the backbone. It uses recursive calls to build
the subtrees “hanging” off the backbone. The backbone has a special property: for each
node v 0 in the path, the successor node in the path is the σi child of v 0 , where i is the item
labeling node v 0 .
The construction of the backbone is done as follows. Using subroutine FindBudget,
MixedGreedy first computes a lower bound B on the minimum additional cost required in
order to achieve a portion α of the goal value Q, assuming we start with partial realization b
(Step 6). This computation is done using the Greedy algorithm of Wolsey (1982) described
in Section A.1 in the Appendix.
After calculating B, MixedGreedy constructs the backbone in two stages, using a different greedy criterion in each to determine which item i to place in the current node.
In the first stage, corresponding to the first repeat loop of the pseudocode, the goal is to
remove weight (probability mass) from the backbone, as cheaply and as soon as possible.
That is, consider a realization a ∈ Γn to be removed from the backbone (or “covered”) if

8

Scenario Submodular Cover

Algorithm 1
Procedure MixedGreedy(g, Q, S, w, c, b)
1: If g(b) = Q then return a single (unlabeled) leaf l
2: Let T be an empty tree
3: N 0 ← {i : bi = ∗}
4: For i ∈ N 0 , σi ← arg min ∆g(b, i, γ)
γ∈Γ
0

→ Z≥0 such that for all U ⊆ N 0 , g 0 (U ) = g(bU ) − g(b), where bU is the extension
of b produced by setting bi = σi for all i ∈ U .
B ← FindBudget(N 0 , g 0 , c), spent ← 0, spent2 ← 0, k ← 1
I ← {i ∈ N 0 |ci ≤ B}
For all R ⊆ I, define DR := {a ∈ S|a  b and ai 6= σiP
for some i ∈ R}
Define h : 2I → Z≥0 such that for all R ⊆ I, h(R) = a∈DR w(a)
R←∅
repeat
among all items i ∈ I
Let i be an item which maximizes h(R∪{i})−h(R)
ci
Let tk be a new node labeled with item i
If k = 1 then make t1 the root of T
else make tk the σj -child of tk−1
j←i
for every γ ∈ Γ such that γ 6= σi do
T γ ← MixedGreedy(g, Q, S, w, c, bi←γ )
Attach T γ to T by making the root of T γ the γ-child of tk
bi ← σi , R ← R ∪ {i}, I ← I − {i}, spent ← spent + ci , k ← k + 1
until spent ≥ B
repeat
i)
Let i be an item which maximizes ∆g(b,i,σ
among all items i ∈ I
ci
Let tk be a node labeled with item i
Make tk the σj -child of tk−1
j←i
for every γ ∈ Γ such that γ 6= σi do
T γ ← MixedGreedy(g, Q, S, w, c, bi←γ )
Attach T γ to T by making the root of T γ the γ-child of tk
bi ← σi , I ← I − {i}, spent2 ← spent2 + ci , k ← k + 1
until spent2 ≥ B or I = ∅
T 0 ← MixedGreedy(g, Q, S, w, c, b); Attach T 0 to T by making the root of T 0 the σj -child of tk−1

5: Define g : 2
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

N0

33: Return T

Procedure FindBudget(I, f, c)
1: Let α = 1 − e−χ ≈ 0.35
P
2: Do a binary search in the interval [0, i∈I ci ] to find the smallest B such that Wolsey’s
greedy algorithm for maximizing a submodular function within a budget of B, applied
to f and the items in I, returns a set of items with utility at least αf (I)
3: Return B

9

Grammel Hellerstein Kletenik Lin

i labels a node in the spine and ai 6= σi ; removing a from the backbone results in the loss
of weight w(a) from the backbone. The greedy choice used in the first stage in Step 12
follows the standard rule of maximizing bang-for-the-buck; the algorithm chooses i such
that the amount of probability mass removed from the backbone, divided by the cost ci , is
maximized. However, in making this greedy choice, it only considers items that have cost
at most B. The first stage ends as soon as the total cost of the items in the chosen sequence
is at least B. For each item i chosen during the stage, bi is set to σi .
In the second stage, corresponding to the second repeat loop, the goal is to increase
utility as measured by g, under the assumption that we already have b, and that the state
of each remaining item i is σi . The algorithm again uses the bang-for-the-buck rule, choosing
the i that maximizes the increase in utility, divided by the cost ci (Step 23). In making
this greedy choice, it again considers only items that have cost at most B. The stage ends
as soon as the total cost of the items in the chosen sequence is at least B. For each item i
chosen during the stage, bi is set to σi .
In Section 2, we defined the value ρ. The way the value B is chosen guarantees that
the updates to b during the two greedy stages cause the value of Q − g(b) to shrink by at
least a fraction ρ before each recursive call. In Appendix A, we prove this fact and use it
to prove the following theorem.
Theorem 1 Mixed Greedy is an approximation algorithm for the Scenario Adaptive Submodular Cover problem that achieves an approximation factor of O( ρ1 log Q).

4. Scenario Mixed Greedy
We now present a variant of Mixed Greedy that eliminates the dependence on ρ in the
approximation bound in favor of a dependence on m, the size of the sample. We call this
variant Scenario Mixed Greedy.
Scenario Mixed Greedy works by first modifying g to produce a new utility function gS ,
and then running Mixed Greedy with gS , rather than g. Utility function gS is produced by
combining g with another utility function hS , using the standard OR construction described
at the end of Section 2. Here hS : (Γ ∪ {∗})n → Z≥0 , where hS (b) = m − |{a ∈ S : a  b}|
and m = |S|. Thus hS (b) is the total number of assignments that have been eliminated
from S because they are incompatible with the partial state information in b. Utility m for
hS is achieved when all assignments in S have been eliminated. Clearly, hS is monotone
and submodular.
When the OR construction is applied to combine g and hS , the resulting utility function gS reaches its goal value Qm when all possible realizations of the sample have been
eliminated or when goal utility is achieved for g.
In an on-line setting, Scenario Mixed Greedy uses the following procedure to determine
the adaptive sequence of items to choose on an initially unknown realization a.
Scenario Mixed Greedy:
1. Construct utility function gS by applying the standard OR construction to g and
utility function hS .
2. Adaptively choose a sequence of items by running Mixed Greedy for utility function
gS with goal value Qm, with respect to the sample distribution DS,w .
10

Scenario Submodular Cover

3. After goal value Qm is achieved, if the final partial realization b computed by Mixed
Greedy does not satisfy g(b) = Q, then choose the remaining items in N in a fixed
but arbitrary order until g(b) = Q.
The third step in the procedure is present because goal utility Q must be reached for g
even on realizations a that are not in S.
Theorem 2 Scenario Mixed Greedy is an approximation algorithm for the Scenario Submodular Cover problem that achieves an approximation factor of O(log Qm), where m is
the size of sample S.
Proof Scenario Mixed Greedy achieves utility value Q for g when run on any realization
a ∈ Γn , because the b computed by Mixed Greedy is such that a  b, and the third step
ensures that Q is reached.
Let c(g) and c(gS ) denote the expected cost of the optimal strategies for the Scenario
SC problems on g and gS respectively, with respect to the sample distribution DS,w . Let τ
be an optimal strategy for g achieving expected cost c(g). It is also a valid strategy for the
problem on gS , since it achieves goal utility Q for g on all realizations, and hence achieves
goal utility Qm for gS on all realizations. Thus c(gS ) ≤ c(g).
The two functions, g and hS , are monotone and submodular. Since the function gS is
produced from them using the standard OR construction, gS is also monotone and submodular. Let ρS be the value of parameter ρ for the function gS . By the bound in Theorem 1,
running Mixed Greedy on gS , for the sample distribution DS,w , has expected cost that is
at most a O( ρ1S log Qm) factor more than c(gS ). Its expected cost is thus also within an
O( ρ1S log Qm) factor of c(g). Making additional choices on realizations not in S, as done
in the last step of Scenario Mixed Greedy, does not affect the expected cost, since these
realizations have zero probability.
Generalizing an argument from Cicalese et al. (2014), we now prove that ρS is lower
bounded by a constant fraction. Consider any b ∈ (Γ ∪ {∗})n and i ∈ N such that bi = ∗,
and any γ ∈ Γ where γ 6= γb,i . Let Cb = |S| − hS (b) = |{a ∈ S | a  b}|. Since the
sets {a ∈ S | a  b and ai = γ} and {a ∈ S | a  b and ai = γb,i } are disjoint, it is not
possible for both of them to have size greater than C2b . It follows that ∆hS (b, i, γ) ≥ C2b
or ∆hS (b, i, γb,i ) ≥ C2b or both. By the construction of gS , it immediately follows that
b
b
∆gS (b, i, γ) ≥ (Q−g(b))C
or ∆gS (b, i, γb,i ) ≥ (Q−g(b))C
or both. Since γb,i is the “worst2
2
case” setting for bi with respect to gS , it follows that ∆gS (b, i, γ) ≥ ∆gS (b, i, γb,i ), and so
b
in all cases ∆gS (b, i, γ) ≥ (Q−g(b))C
. Also, (Q − g(b))Cb = Qm − gS (b). Therefore, ρS ≥ 21 .
2
The theorem follows from the bound given in Theorem 1.

5. Scenario Adaptive Greedy
Scenario Adaptive Greedy works by first constructing a utility function gW , produced by applying the standard OR construction
to g and utility function hW . Here hW : (Γ ∪ {∗})n →
P
Z≥0 , where hW (b) = W − a∈S:ab w(a). Intuitively, hW (b) is the total weight of assignments that have been eliminated from S because they are incompatible with the partial
11

Grammel Hellerstein Kletenik Lin

state information in b. Utility W is achieved for hW when all assignments in S have been
eliminated. It is obvious that hW is monotone and submodular. The function gW reaches
its goal value QW when all possible realizations of the sample have been eliminated or
when goal utility is achieved for g. Once gW is constructed, Scenario Adaptive Greedy runs
Adaptive Greedy on gW .
In an on-line setting, Scenario Adaptive Greedy uses the following procedure to determine the adaptive sequence of items to choose on an initially unknown realization a.
Scenario Adaptive Greedy:
1. Construct modified utility function gW by applying the standard OR construction to
g and utility function hW .
2. Run Adaptive Greedy for utility function gW with goal value QW , with respect to
sample distribution DS,w , to determine the choices to make on a.
3. After goal value QW is achieved, if the partial realization b representing the states of
the chosen items of a does not satisfy g(b) = Q, then choose the remaining items in
N in arbitrary order until g(b) = Q.
In Appendix C, we prove the following lemma.
Lemma 3 Utility function gW is adaptive submodular with respect to sample distribution
DS,w .
The consequence of Lemma 3 is that we may now use any algorithm designed for adaptive
submodular utility functions. This gives us Theorem 4.
Theorem 4 Scenario Adaptive Greedy is an approximation algorithm for the Scenario
Adaptive Submodular Cover problem that achieves an approximation factor of O(log QW ),
where W is the sum of the weights on the realizations in S.
Proof Since gW is produced by applying the OR construction to g and hW , which are
both monotone, so is gW . By Lemma 3, gW is adaptive submodular with respect to the
sample distribution. Thus by the bound of Golovin and Krause on Adaptive Greedy, running that algorithm on gW yields an ordering of choices with expected cost that is at most a
O(log QW ) factor more than the optimal expected cost for gW . By the analogous argument
as in the proof of Theorem 2, it follows that Scenario Adaptive Greedy solves the Scenario
Submodular Cover problem for g, and achieves an approximation factor of O(log QW ).

Acknowledgments
L. Hellerstein thanks Andreas Krause for useful discussions at ETH, and especially for
directing our attention to the bound of Streeter and Golovin for min-sum submodular
cover.

12

Scenario Submodular Cover

References
G. Bellala, S. Bhavnani, and C. Scott. Group-based active query selection for rapid diagnosis
in time-critical situations. IEEE Transactions on Information Theory, 2012.
Y. Ben-Dov. Optimal testing procedure for special structures of coherent systems. Management Science, 1981.
M.-F. Chang, W. Shi, and W. K. Fuchs. Optimal diagnosis procedures for k-out-of-n
structures. IEEE Transactions on Computers, 39(4):559–564, April 1990.
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew Bagnell, Siddhartha S. Srinivasa,
and Andreas Krause. Submodular surrogates for value of information. In Proceedings
of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015,
Austin, Texas, USA., pages 3511–3518, 2015a.
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew Bagnell, Siddhartha S. Srinivasa,
and Andreas Krause. Submodular surrogates for value of information (long version).
2015b. URL http://las.ethz.ch/files/chen15submsrgtvoi-long.pdf.
Ferdinando Cicalese, Eduardo Laber, and Aline Medeiros Saettler. Diagnosis determination:
decision trees optimizing simultaneously worst and expected testing cost. In Proceedings
of The 31st International Conference on Machine Learning, pages 414–422, 2014.
A. Deshpande, L. Hellerstein, and D. Kletenik. Approximation algorithms for stochastic
boolean function evaluation and stochastic submodular set cover. In Symposium on
Discrete Algorithms, 2014.
D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active
learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427–
486, 2011.
D. Golovin, A. Krause, and D. Ray. Near-optimal Bayesian active learning with noisy
observations. In 24th Annual Conference on Neural Information Processing Systems
(NIPS), pages 766–774, 2010.
Andrew Guillory and Jeff A. Bilmes. Simultaneous learning and covering with adversarial
noise. In Proceedings of the 28th International Conference on Machine Learning, ICML
2011, Bellevue, Washington, USA, June 28 - July 2, 2011, pages 369–376, 2011.
Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, Drew Bagnell, and Siddhartha S. Srinivasa. Near optimal bayesian active learning for decision making. In
Proceedings of the Seventeenth International Conference on Artificial Intelligence and
Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014, pages 430–438, 2014.
H. Kaplan, E. Kushilevitz, and Y. Mansour. Learning with attribute costs. In Symposium
on the Theory of Computing, pages 356–365, 2005.
S. Salloum. Optimal testing algorithms for symmetric coherent systems. PhD thesis, University of Southern California, 1979.
13

Grammel Hellerstein Kletenik Lin

S. Salloum and M. Breuer. An optimum testing algorithm for some symmetric coherent systems. Journal of Mathematical Analysis and Applications, 101(1):170 – 194, 1984. ISSN
0022-247X. doi: 10.1016/0022-247X(84)90064-7. URL http://www.sciencedirect.
com/science/article/pii/0022247X84900647.
Martin Skutella and David P. Williamson. A note on the generalized min-sum set cover
problem. Operations Research Letters, 39(6):433 – 436, 2011.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular
functions. In Advances in Neural Information Processing Systems, pages 1577–1584,
2009.
Tonguç Ünlüyurt. Sequential testing of complex systems: a review. Discrete Applied Mathematics, 142(1-3):189–205, 2004.
Laurence Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics
for location problems. Mathematics of Operations Research, 7(3):410–425, 1982.

Appendix A. Proof of Bound for Mixed Greedy
We first discuss the algorithm of Wolsey used in FindBudget.
A.1. Wolsey’s Greedy Algorithm for Budgeted Submodular Cover
The Budgeted Submodular Cover problem takes as input a finite set N of items, a positive
integer B > 0 called the budget, a monotone submodular set function f : 2N → Z≥0 , and
a vector c indexed by the itemsP
in N , such that ci ∈ R≥0 for all i ∈ N . The problem is to
find a subset R ⊆ N such that i∈R ci ≤ B, and f (R) is maximized.
Wolsey (1982) developed a greedy approximation algorithm for this problem. We present
the pseudocode for this algorithm here, together with Wolsey’s approximation bound.
Procedure WolseyGreedy(N, f, c, B)
1: spent ← 0, R ← ∅, k ← 0
2: repeat
3:
k ←k+1
(R)
4:
Let ik be the i ∈ N that minimizes f (R∪{i})−f
among all i ∈ N with ci ≤ B
ci
5:
N ← N − {i}, spent ← spent + ci , R ← R ∪ {ik }
6: until spent > B or N = ∅
7: if f ({ik }) ≥ f (R − {ik }) then
8:
return {ik }
9: else
10:
return R − {ik }

Lemma 5 (Wolsey (1982)) Let R∗ be the optimal solution to the Budgeted Submodular
Cover problem on instance (N, f, c, B). Let R = {i1 , . . . , ik } be the set of items chosen by
running Wolsey-Greedy(N, f, c, B). Let e be the base of the natural logarithm, and let χ be
the solution to eχ = 2 − χ. Then f (R) ≥ (1 − e−χ )f (R∗ ).
14

Scenario Submodular Cover

A.2. Analysis of Mixed Greedy
Consider a Scenario SC instance (g, Q, S, w, c), and a partial realization b ∈ (Γ ∪ {∗})n . We
now consider MixedGreedy(g, Q, S, w, c, b). It constructs a tree for the Scenario SC instance
induced by b. In this induced instance, the item set is N 0 = {i | bi = ∗}. Without loss of
generality, assume that N 0 = {1, . . . , n0 } for some n0 . For d ∈ (Γ ∪ {∗})n such that d  b,
0
define ν(d) be the restriction of d to the items in N 0 . For d0 ∈ (Γ ∪ {∗})n , ν −1 (d0 ) denotes
the extension d  d0 to all elements in N such that di = d0i for i ∈ N 0 and di = bi otherwise.
0
The utility function g 0 : (Γ ∪ {∗})n → Z≥0 for the instance induced by b is a function on
0
partial realizations d0 of the items in N 0 . Specifically, for d0 ∈ (Γ∪{∗})n , g 0 (d0 ) = g(ν −1 (d0 )).
The sample S 0 in the induced instance consists of the restrictions of the realizations in
{a ∈ S | a  b} to the items in N 0 . That is, S 0 = {ν(a) | a ∈ S, a  b}. Note that each
realization in S 0 corresponds to a unique realization in S. The weight function w0 for the
induced instance is such that for all d0 ∈ S 0 , w0 (d0 ) = w(ν −1 (d0 )). The goal value for the
induced instance is Q.
If g(b) = Q, then MixedGreedy(g, Q, S, w, c, b) returns the optimal tree for the instance
induced by b, which is a single (unlabeled) leaf with expected cost 0. Assume g(b) < Q.
For any decision tree τ for the induced instance and
P any realization a defined over the
item set N 0 (or over any superset of N 0 ), let κ(τ, a) = i∈M ci , where M is the set of items
labeling the nodes on the root-leaf path followed in τ on realization a. That is, κ(τ, a) is
the cost incurred when using tree τ on realization a.
Let τ ∗ be a decision tree that is an optimal solution for the induced instance. Let
C ∗ = E[κ(τ ∗ , a)] where a is a random realization drawn from DS 0 ,w0 . Thus C ∗ is the
expected cost of an optimal solution to the induced instance. Let τ G denote the tree output
by running MixedGreedy(g, Q, S, w, c, b).
0
Let σ ∈ Γn be such that for i ∈ N 0 , σi = arg min g(bi←γ ). Thus, σ is the realization
γ∈Γ

whose entries are computed in Step 4 of MixedGreedy.
For each node v in the tree τ G , let p̃(v) denote the probability that node v will be
reached when using τ G on a random realization a drawn from DS 0 ,w0 . Let cv = ci where
i is the item labeling node v. Consider the backbone constructed during the call to
MixedGreedy(g, Q, S, w, c, b). The backbone consists of the nodes created during the two
repeat loops in this call,
P excluding the recursive calls. Let Y be the set of nodes in the
backbone. Let cY = v∈Y p̃(v)cv . Thus cY is the contribution of the nodes in the backbone to the expected cost of tree τ G . The following lemma says that this contribution is no
more than a constant times the expected cost of the optimal tree τ ∗ .
Lemma 6 cY ≤ 24C ∗ .
Lemma 6 is the key technical lemma in our analysis, and it is the proof of this lemma
that constitutes the major difference between our analysis and the analysis in Cicalese et al.
(2014). We defer the proof of this lemma to Section A.3. Using this lemma, it is easy to
generalize the rest of the analysis of Cicalese et al. to obtain the proof of Theorem 1. The
proofs in the remainder of this section closely follow the proofs in Cicalese et al. We present
them so that this paper will be self-contained.

15

Grammel Hellerstein Kletenik Lin

Let B be the budget that is computed in Line 6, with FindBudget, when running
MixedGreedy(g, Q, S, w, c, b). Recall the constant α defined in FindBudget, based on the
bound on Wolsey’s Greedy algorithm (Lemma 5).
Lemma 7 The condition at the end of the first repeat loop (spent ≥ B) will be satisfied.
Also, κ(τ ∗ , σ) ≥ B.
Proof Trees τ G and τ ∗ must achieve utility Q − g(b) on realization σ. The binary search
procedure in FindBudget finds the least budget B allowing Wolsey’s greedy algorithm to
achieve a total increase in utility of at least α(Q − g(b)), on realization σ. It follows from
the bound on Wolsey’s greedy algorithm (Lemma 5) that on realization σ, an increase of
α(Q − g(b)) could not be achieved with a budget smaller than B. Thus, κ(τ ∗ , σ) ≥ B.
The next lemma clearly holds because in the two repeat loops, we only consider items
of cost at most B, and we continue choosing items of cost at most B until a budget of B is
met or exceeded.
Lemma 8

P

v∈Y

cv ≤ 4B.

Let bf inal denote the final value of b in the last recursive call, in Line 32, when running
MixedGreedy(g, Q, S, w, c, b).
Lemma 9 g(bf inal ) ≥ g(b) + 19 (Q − g(b)).
Proof Recall that N 0 = {1, . . . , n0 }. For any D ⊆ N 0 , let σ̂ D denote the extension of b,
to (Γ ∪ {∗})n , such that σ̂iD = σi (as specified in line 4 of MixedGreedy(g, Q, S, w, c, b)) for
i ∈ D, and σ̂iD = bi otherwise.
It follows from the way that B was computed in FindBudget, and the fact that the
value of g P
is Q on any (full) realization of the items in N , that there is a subset L ⊆ N 0
such that i∈L ci = B and g(σ̂ L ) ≥ α(Q − g(b)) + g(b).
Let Y1 and Y2 be the set of items i chosen in the first and second repeat loops respectively.
Thus bf inal = σ̂ Y1 ∪Y2 .
Let d1 = g(σ̂ Y1 ) − g(b) represent the utility gained in the first repeat loop. Let
d2 = g(σ̂ Y1 ∪L ) − g(σ̂ Y1 ) represent the additional utility that the items in L \ Y1 would
provide. Since g(σ̂ L ) ≥ α(Q − g(b)) + g(b) and g is monotone, g(σ̂ Y1 ∪L ) ≥ g(σ̂ L ), and thus
g(σ̂ Y1 ∪L ) ≥ α(Q − g(b)) + g(b). So d1 + d2 ≥ α(Q − g(b)). At the end of the first repeat loop
the items in Y1 have been chosen. If we were to add the items in L\Y1 to those in Y1 , it would
increase the utility by d2 ≥ α(Q − g(b)) − d1 . Since the items in the second repeat loop are
chosen greedily with respect to g (and c) until budget B is met or exceeded, or goal value Q
is attained, it follows by the approximation bound on Wolsey’s algorithm (Lemma 5) that
the amount of additional utility added during the second repeat loop is at least α times the
amount of additional utility that would be added by instead choosing the items in L\Y1 . We
thus have g(σ̂ Y1 ∪Y2 ) − g(σ̂ Y1 ) ≥ αd2 . Adding d1 to both sides, from the definition of d1 we
get g(σ̂ Y1 ∪Y2 ) − g(b) ≥ d1 + αd2 . We know from above that d2 ≥ α(Q − g(b)) − d1 so we have
g(σ̂ Y1 ∪Y2 ) − g(b) ≥ d1 + α (α (Q − g(b)) − d1 ) ≥ d1 + α2 (Q − g(b)) − αd1 ≥ α2 (Q − g(b)).
The lemma follows because the constant α2 is greater than 91 .
16

Scenario Submodular Cover

We can now give the proof of Theorem 1, stating that the Mixed Greedy algorithm
achieves an approximation factor of O( ρ1 log Q).
Proof of Theorem 1 The Mixed Greedy algorithm solves the Scenario SC instance
(g, Q, S, w, c) by running recursive function MixedGreedy(g, Q, S, w, c, b). In the initial call,
b is set to ∗n .
Let τ G denote the tree that is output by running MixedGreedy(g, Q, S, w, c, b). Let τ ∗
denote the optimal tree for the Scenario SC instance induced by b.
The expected cost of τ G can be broken into the part that is due to costs incurred on items
in the backbone in the top-level call to the MixedGreedy function, and costs incurred in the
subtrees built in the recursive calls to MixedGreedy. The recursive calls in Steps 18 and 28
build subtrees of τ G that are rooted at a γ-child of a node labeled i, such that γ 6= σi . It
follows from the definition of ρ that the value of the partial realization used in each of these
recursive calls, bi←γ is such that g(bi←γ )−g(b) ≥ ρ(Q−g(b)), so g(bi←γ ) ≥ ρ(Q−g(b))+g(b),
The remaining recursive call is performed on bf inal , and by Lemma 9, g(bf inal ) ≥ 91 (Q −
g(b)).
Let η = min{ρ, 91 }. Let b1 , . . . , bt denote the partial realizations on which the recursive
calls are made, and for which the value of g on the partial realization is strictly less than
Q. These are the recursive calls which result in the construction of non-trivial subtrees,
with non-zero cost. Note that b1 , . . . , bt may include bf inal . For all j ∈ {1, . . . , t}, g(bj ) ≥
η(Q − g(b)) + g(b), or equivalently
Q − g(bj ) ≤ (1 − η)(Q − g(b))

(1)

For j ∈ {1, . . . , t}, let τjG denote the tree returned by the recursive call on bj .
Let S 0 be the sample for the Scenario SC instance induced by b, so S 0 = {ν(a) | a ∈ A}.
Let w0 be the weight function for that induced instance. Let Aj = {ν(a) | a ∈ S, a  bj }.
Let µ∗j denote an optimal decision tree for the Scenario SC instance induced by bj . Consider
the optimal decision tree τ ∗ for the instance induced by b, and use it to form a decision
tree τj∗ for the instance induced by bj as follows: for each item i such that bi = ∗ and
bji 6= ∗, fix i to have state bji in the tree. That is, for any node in the tree labeled i,
delete all its children except the one corresponding to state bji , and then delete the node,
connecting the parent of the node to its one remaining child. Since µ∗j is optimal for the
induced problem, τj∗ cannot
lower expected cost for this problem. It follows that
P
P have
0 (a)κ(τ ∗ , a) ≥
0 (a)κ(µ∗ , a). Further, since κ(τ ∗ , a) ≥ κ(τ ∗ , a) for any
w
w
j
j
j
a∈Aj
a∈Aj
a ∈ Aj ,
X
X
w(a)κ(τ ∗ , a) ≥
w0 (a)κ(µ∗j , a).
(2)
a∈Aj

a∈Aj

From the description of MixedGreedy, it is easy to verify that the Aj are disjoint subsets
of S 0 . Therefore,
t X
X
X
w0 (a)κ(τ ∗ , a) =
w0 (a)κ(τ ∗ , a)
a∈S 0

j=1 a∈Aj

0
0
Let W =
a∈S 0 w (a). For a ∈ S , let p(a) be the probability assigned to a by
0
distribution DS 0 ,w0 , so p(a) = w (a)/W . Let cY be the sum of the costs incurred on

P

17

Grammel Hellerstein Kletenik Lin

0
0
the backbone of τ G as in
P 6. Taking expectations with respect to DS ,w , we
P Lemma
have E[κ(τ G , a)] = cY + tj=1 abj p(a)κ(τjG , a). We can now bound the ratio between
G = E[κ(τ G , a)] and C ∗ = E[κ(τ ∗ , a)].

P
0
G
G
a∈S 0 w (a)κ(τ , a)
P
=
0
∗
C∗
a∈S 0 w (a)κ(τ , a)
Pt P
W cY + j=1 a∈Aj w0 (a)κ(τjG , a)
P
=
0
∗
a∈S 0 w (a)κ(τ , a)
Pt P
0
G
W cY
j=1
a∈Aj w (a)κ(τj , a)
P
=P
+
0
∗
0
∗
a∈S 0 w (a)κ(τ , a)
a∈S 0 w (a)κ(τ , a)
Pt P
0
G
j=1
a∈Aj w (a)κ(τj , a)
P
≤ 24 +
0
∗
a∈S 0 w (a)κ(τ , a)
Pt P
0
G
j=1
a∈Aj w (a)κ(τj , a)
= 24 + Pt P
0
∗
j=1
a∈Aj w (a)κ(τ , a)
P
0
G
a∈A w (a)κ(τj , a)
≤ 24 + max P j 0
∗
j
a∈Aj w (a)κ(µj , a)

by Lemma 6

In the last line, we substitute κ(τ ∗ , a) with κ(µ∗j , a) because of (2), and we use the max
because of the fact that

P
P xi
yi

≤ max xyii for xi , yi > 0.
i

As described above, for each j, the recursive call to MixedGreedy on b = bj constructs
a tree τjG for a Scenario SC instance I 0 induced by bj , with goal value Q − g(bj ). The tree
P

µ∗j

is an optimal tree for instance

I 0.

It follows that the ratio

a∈Aj 0

P

a∈Aj

Gj
∗
Cj∗ , where Gj and Cj
Gj
G
C ∗ ≤ 24 + maxj Cj∗ .

w(a)κ(τjG ,a)
w(a)κ(µ∗j ,a)

is equal to

are the values of C ∗ and G for the induced instance I 0 . Thus we have

We now prove that CG∗ ≤ 1 + 24 η1 ln(Q − g(b)), when g(b) < Q, by induction on the
total number of items n = |N |. The base case n = 1 clearly holds. Assume inductively that
G
1
C ∗ ≤ 1 + 24 η ln(Q − g(b)) when the number of items is less than n, where Q is the goal
value. Then for n items, we have CG∗ ≤ 24 + (1 + 24 η1 (ln(Q − g(bj )))) for the j maximizing
Gj
Cj∗ .

By (1), Q − g(bj ) ≤ (1 − η)(Q − g(b)) so


G
1
≤ 24 + 1 + 24 ln((1 − η)(Q − g(b))
C∗
η


1
≤ 1 + 24 1 + ln((1 − η)(Q − g(b))
η


1
1
= 1 + 24 1 + ln(1 − η) + ln(Q − g(b))
η
η
18

Scenario Submodular Cover

1
≤ 1 + 24 ln(Q − g(b))
η
where the last inequality holds because 1−η ≤ e−η so log(1−η) ≤ −η and thus η1 ln(1−η) ≤
−1.
Since Q ≥ Q − g(b), the expected cost of the greedy tree τ G constructed by the Mixed
Greedy algorithm is within an O( η1 ln Q) factor of the expected cost of the optimal tree.
Also, since η = min{ρ, 91 }, we know that η1 is either constant or it is equal to ρ1 . We therefore
have that the expected cost of τ G is within an O( ρ1 log Q) factor of the expected cost of the
optimal tree.

A.3. Proof of Lemma 6
We now present our proof bounding the expected cost incurred on the backbone of the
greedy tree. Our proof relies heavily on the work of Streeter and Golovin (2009) on the
Min-Sum Submodular Cover problem. We use some of their terminology and definitions in
our proof.
A.3.1. Definitions
We begin by defining a discrete version of the Min-Sum Submodular Cover problem. Let
N = {1, . . . , n} be a set of items, and let c ∈ Zn≥0 be a non-negative integer vector of “times”
associated with those items. Let f : 2N → Z≥0 be a monotone, submodular utility function
and let Q = f (N ). We define a schedule to be a finite sequence S = h(i1 , τ1 ), . . . , (im , τm )i
of pairs in N × R≥0 and refer to τj as thePtime to process item ij .
For a schedule S, we define `(S) = j≥1 τj to be the sum of the times spent on all
items in S. Given a schedule S = h(v1 , τ1 ), (v2 , τ2 ), . . . i, we define Shti to be the schedule
such that for t ≤ `(S),
P
Shti = h(v1 , τ1 ), (v2 , τ2 ), . . . , (vk , τk ), (vk+1 , t − ki=1 τi )i
P
where k = max{j : ji=1 τi < t}. For t > `(S), we let Shti = S. We refer to Shti as S
truncated at time t.
1
Let f c denote the function defined on schedules S such that f c (S) = f (N
) f ({i | (i, ci ) ∈
S}). Thus, the only pairs (i, τ ) in the schedule that contribute to the value of f c are those
for which τ = ci . Where c is understood, we will omit the superscript and use f to denote
both the original utility function on 2N , and the function f c which is defined on schedules.
We define the cost of schedule S, with respect to f and c, to be
Z `(S)
cost(f c , S) =
1 − f c (Shti )dt
(3)
t=0

We define the Discrete Min-Sum Submodular Cover Problem on f and c to be the
problem of finding a schedule S that achieves f c (S) = 1 with minimum cost.
Streeter and Golovin presented a greedy algorithm for the general Min-Sum Submodular
Cover problem. In Discrete Min-Sum Submodular Cover, a pair (i, τ ) can only contribute
to the utility of a schedule if τ = ci . The general problem studied by Streeter and Golovin
does not have this restriction.
19

Grammel Hellerstein Kletenik Lin

A.3.2. Standard Greedy Algorithm for Discrete Min-Sum Submodular
Cover
The algorithm of Streeter and Golovin for the general Min-Sum Submodular Cover problem
uses a standard greedy approach. It adds pairs (i, τ ) iteratively to the end of an initially
empty schedule, using the greedy rule of choosing the pair that will result in the largest
increase in utility per unit time. We call this algorithm Standard Greedy.
We restrict our attention to the Discrete Min-Sum Submodular Cover problem. Applied
to this problem, Standard Greedy uses the greedy rule of choosing the pair (i, ci ) that will
result in the largest increase in utility as measured by f c , per unit time. The algorithm
ends when the constructed schedule S satisfies f c (S) = 1.
More formally, Standard Greedy uses the greedy rule below to construct a greedy schedule G = h(g1 , τ1 ), (g2 , τ2 ), . . . i, where each gj = i for some i ∈ N , and τi = ci . Since each τi
is determined by gi , we drop the τi from the description of the schedule, and consider G to
be simply a list of actions g = hg1 , g2 , . . . , i.
We define Gj = hg1 , g2 , . . . gj−1 i, where G1 = h i. The action gj chosen using the greedy
rule is as follows (using ⊕ to represent the concatenation of two schedules):


f (Gj ⊕ h(i, ci )i) − f (Gj )
gj = arg max
(4)
ci
(i,ci )|i∈N
The following theorem of Streeter and Golovin shows that the schedule constructed by
Standard Greedy has a cost that is within a factor of 4 of the cost achieved by any schedule
(including the optimal schedule).
Theorem 10 (Streeter and Golovin (2009)) Let I be an instance of the Discrete MinSum Submodular Cover problem with time vector c, monotone submodular utility function
f , and item set N . Let S denote the set of all schedules S for item set N and cost vector
c that satisfy f c (S) = 1. Let G be the schedule constructed by running Standard Greedy
algorithm on instance I. Then for all S ∈ S, cost(f c , G) ≤ 4 cost(f c , S).
A.3.3. Bound on Cost of MixedGreedy
We now return to our analysis of MixedGreedy(g, Q, S, w, c, b). As part of our analysis, we
will prove a result similar to Theorem 10.
Without loss of generality,
assume that b = ∗n .
P
Recall that cY = v∈Y p̃(v)cv , where Y is the set of nodes in the backbone, p̃(v) is
the probability that a random realization will reach node v, and cv is the cost of the item
labeling node v. Let S Y = h(i1 , ci1 ), . . . , (ik−1 , cik−1 )i be the schedule such that i1 , . . . , ik−1
is the sequence of items labeling the nodes in the backbone, from the top of the backbone
and moving downwards.
P
Define a utility function hp : 2N → R≥0 such that for R ∈ 2N , hp (R) = 1 − aσR p(a),
where σ R is the realization in Γn such that σiR = σi for i ∈ R, and σiR = ∗ otherwise.
The
P
function hp is clearly monotone and submodular. Additionally, we can see that v∈Y p̃(v)cv
is the cost of schedule S Y with respect to utility function utility function hp .
Recall that τ ∗ denotes the optimal strategy solving the Scenario Submodular Cover
instance on g and c. Consider the sequence j1 , . . . , jt of items chosen by τ ∗ on realization σ.
20

Scenario Submodular Cover

Let S ∗ = h(j1 , cj1 ), . . . , (jt , cjt )i. The schedule S Y created by MixedGreedy is constructed
greedily, using the same type of greedy rule as in (4). However, S Y is constructed in two
stages: the first stage greedily chooses with respect to hp , and the second chooses greedily
with respect to an entirely different utility function. We therefore cannot directly apply
Theorem 10 to bound the cost of schedule S Y . We deal with this by using an approach
analogous to one used by Cicalese et al. (2014) (in the analysis of their Equivalence Class
Determination algorithm) that allows us to concentrate only on the cost of the portion of
the schedule constructed during the first stage.
To do this, we note that schedule S Y can be expressed as the concatenation of two
schedules, S 1 and S 2 , where S 1 contains the ij chosen during the first repeat loop, with
their P
costs, and S 2 contains the ij chosen during the second, also with their costs. Recall
that v∈Y p̃(v)cv is the cost of schedule S Y with respect to hp . We can express this cost
as follows:
X
v∈Y

Z

`(S 1 )

1−

p̃(v)cv =
t=1

1
hp (Shti
)dt

Z

`(S 2 )

+
t=0

2
1 − hp (S 1 ⊕ Shti
)dt

Note that `(S 2 ) ≤ 2B, since we have assumed that each ci ≤ B, and the second repeat
loop of MixedGreedy ends as soon as the last item added causes the length of S 2 to exceed
B. Since hp is monotone, the value of the second integral is at most 2B(1 − hp (S 1 )), and
the value of the first integral is at least B(1 − hp (S 1 )) because `(S 1 ) ≥ B. It follows that
the value of the second integral is at most twice the value of the first, so we have
X
v∈Y

Z

`(S 1 )

p̃(v)cv ≤ 3
t=0

1
1 − hp (Shti
)dt

which yields the following inequality, allowing us to bound the total cost of S Y by analyzing
the cost of S 1 .
cost(hp , S Y ) ≤ 3 cost(hp , S 1 )
(5)
R `(S 1 )
1 )dt, which is the cost
Therefore, to prove Lemma 6, it suffices to bound t=0 1 − hp (Shti
of schedule S1 with respect to hp .
Schedule S 1 selects items greedily with respect to hp . However, we cannot apply Theorem 10 to bound the cost of S1 in terms of the cost of S ∗ , because only items of cost at
most B are considered in greedily forming S 1 , while items of cost greater than B may be
included in S ∗ .
∗ .
We will instead bound the cost of S 1 in terms of the cost of the truncated schedule ShBi
To do this, we will prove a lemma that is similar to Theorem 10. We defer its proof to the
next section, since it is somewhat technical and is similar to the proof of Theorem 10. The
definitions of Gj and d are as given in the previous section.
The statement of the lemma is as follows.
Lemma 11 Let I be an instance of the Discrete Min-Sum Submodular Cover problem with
time vector c, utility function f , and item set N . Let S denote the set of all schedules S for
item set N and cost vector c satisfying f c (S) = f (N ). Let G = hg1 , g2 , . . . i be the schedule
21

Grammel Hellerstein Kletenik Lin

constructed by running Standard Greedy on instance I and let Gj = hg1 , g2 , . . . gj−1 i, where
G1 = h i. Let B ∈ R be such that `(G) ≥ B and let d be the maximum j such that
`(Gj ) < B. For any schedule S ∈ S, cost(f, Gd ) ≤ 4 cost(f, ShBi ). Further, cost(f, Gd+1 ) ≤
8 cost(f, ShBi ).
We now show how to use Lemma 11 to prove Lemma 6.
∗
Let m be such that ShBi
= h(j1 , cj1 ), . . . , (jm−1 , cjm−1 ), (jm , τjm )i. By the definition of
∗
schedule truncation, τjm ≤ cjm . Since the length of ShBi
is B, each of cj1 , . . . , cjm−1 is at
most B, but it is possible that cjm > B.
Consider a restricted version I 0 of our current Min-Sum Submodular Cover instance I
in which we include only those items i ∈ N such that ci ≤ B. Let N 0 be the set of those
items. Let S 0 be the schedule that results from concatenating h(j1 , cj1 ), . . . , (jm−1 , cjm−1 )i
with an arbitrary sequence of pairs (i, ci ) with i ∈ N 0 , such that hp (S 0 ) = hp (N 0 ). Let
0
∗ , both have the same first
to ShBi
`0 denote `(h(j1 , cj1 ), . . . , (jm−1 , cjm−1 i). Comparing ShBi
∗
0
m − 1 elements. Schedule ShBi
then has (jm , τjm ) where τjm = B − `0 , whereas schedule ShBi
may then have multiple elements in N 0 × Z≥0 which together have length B − `0 . Because
R
∗
∗ ) = B 1 − h (S ∗ )dt,
hp is monotone, and the cost of hp on schedule ShBi
is cost(hp , ShBi
p hti
t=0
0
and analogously for ShBi , it immediately follows that
0
∗
cost(hp , ShBi
) ≤ cost(hp , ShBi
)

(6)

Now consider the schedule S 1 that is computed during the the first stage of running
MixedGreedy. Let G0 be the greedy schedule produced by running the Greedy algorithm
on instance I 0 , with utility function hp and times c. Because only items i with ci ≤ B are
considered when S 1 is constructed, and items are chosen greedily with respect to hp , S 1 is
a prefix of G0 .
Let d be such that S 1 = h(i1 , ci1 ), . . . , (id , cid )i. Thus, S 1 = G0d+1 . in particular, we
have that `(S 1 ) ≥ B and `(h(i1 , ci1 ), . . . , (id−1 , cid−1 )i) < B. It follows from (6) and from
Lemma 11 that
0
∗
cost(hp , S 1 ) ≤ 8 cost(hp , ShBi
) ≤ 8 cost(hp , ShBi
)
(7)
and therefore
cost(hp , S 1 ) ≤ 8 cost(hp , S ∗ )
C∗

(8)

We have that cost(hp , S Y ) ≤ 3 cost(hp , S 1 ). We also have that cY = cost(hp , S Y ) and
= cost(hp , S ∗ ). Therefore, we have
cY = cost(hp , S Y ) ≤ 3 cost(hp , S 1 ) ≤ 24 cost(hp , S ∗ ) = 24C ∗

A.4. Proof of Lemma 11, approximation bounds for truncated schedules
We prove Lemma 11, which states that the following two properties hold:
Property 1: cost(f, Gd ) ≤ 4 cost(f, ShBi )
22

Scenario Submodular Cover

Property 2: cost(f, Gd+1 ) ≤ 8 cost(f, ShBi )
The proof is similar to the proof of Streeter and Golovin for Theorem 10. 3 We will
assume that f : 2N → [0, 1]. We can transform any f : 2N → R≥0 into a function of this
(S)−f (∅)
type by scaling f so that for all S ∈ 2N , the scaled version of f (S) is equal to ff(N
)−f (∅) .
1
c
c
Recall that f is the function defined on schedules S such that f (S) = f (N ) f ({i |
(i, ci ) ∈ S}). We call f c a job. We refer to a pair (i, τ ) ∈ N × R≥0 as an action and to τ as
the time taken by that action.
As in Section A.3, let G = h(g1 , τ1 ), (g2 , τ2 ), . . . i, denote the schedule computed by the
Greedy algorithm on I and let Gj = hg1 , g2 , . . . gj−1 i. et S be an arbitrary schedule for the
instance with f (S) = f (N ). Let d be the maximum j such that `(Gj ) < B.
We may assume without loss of generality that for every (i, τ ) in S, τ = ci , since f c
does not gain any value from pairs (i, τ ) with τ 6= ci . As before, we will generally omit the
superscript on f c and simply write f (S).
We begin by showing that Property 1 implies Property 2.
Property 1 ⇒ Property 2: We define fGd (S), a new function defined on schedules that is
derived from f . Intuitively, Gd completes some portion of the job f ; we wish to consider the
portion of the job that remains to be completed after the actions in Gd have been performed.
The function fGd (S) is defined to be the portion of the job completed by first executing
schedule Gd and then executing schedule S. We express this as fGd (S) = f (Gd ⊕ S). Note
that fGd still satisfies the essential conditions for a job as it is monotone and submodular.
It should be noted, however, that unless f (Gd ) = 0, then fGd (hi) 6= 0 (equivalently, due to
monotonicity, there is no schedule S for which fGd (S) = 0).
It is easy to show that the cost(fGd , S) represents the additional cost incurred by schedule
S on job f after the schedule Gd has already been executed.
Z `(S)

cost(fGd , S) =
1 − fGd (Shti ) dt
t=0
`(S)

Z


1 − f (Gd ⊕ Shti ) dt

=

t=0
`(Gd ⊕S) 

Z
=

t=`(Gd )
`(Gd ⊕S) 

Z
=

t=0



1 − f (Gd ⊕ S)hti dt


1 − f (Gd ⊕ S)hti



Z

`(Gd )

dt −


1 − f (Gd hti ) dt

t=0

Therefore, we have
cost(f, Gd ) + cost(fGd , S) = cost(f, Gd ⊕ S)

(9)

Property 1 asserts that cost(f, Gd ) ≤ 4 cost(f, ShBi ) for any schedule S ∈ S. STOPPED
HERE Also from this assumption, the greedy schedule for fGd is within a factor of 4 of
any other schedule for fGd . Additionally, if we look at only the first action of the greedy
3. Although we give a proof only for Discrete Min-Sum Submodular Cover, the proof can easily be adapted
to give the same result for the more general Min-Sum Submodular Cover problem considered by Streeter
and Golovin.

23

Grammel Hellerstein Kletenik Lin

schedule for fGd (i.e. action gd ), the cost incurred by this one action is less than that of
the entire greedy schedule for fGd , which in turn is less than 4 times any other schedule for
∗ ). Therefore, we have
fGd . Thus, we also have that cost(fGd , hgd i) ≤ 4 cost(fGd , ShBi
cost(f, Gd+1 ) = cost(f, Gd ) + cost(fGd , hgd i)
≤
≤

∗
)
4 cost(f, ShBi
∗
8 cost(f, ShBi )

+

(by (9))

∗
)
4 cost(fGd , ShBi

∗ ) ≤ cost(f, S ∗ ).
since, by the monotonicity of f , cost(fGd , ShBi
hBi

Proof of Property 1: We first define a few values. The quantity Rj = 1−f (Gj ) represents
how much of our task remains to be completed before the jth item of the greedy schedule
is chosen. We define sj to be the “bang for the buck” earned from that item. That is,
(R −R
)
R
p
sj = j τj j+1 . Then, let pj = sjj for all j ≤ d, and pj = 0 for j > d. Let xj = 2j and let
R

∗ ).
yj = 2j . Also, let ψ(x) = 1 − f (Shxi
In order to prove the theorem, we wish to show
Z B 
Z B

1
∗
1 − f (Shti
) dt =
ψ(x) dx ≥ cost(f, Gd )
4
t=0
x=0

We need to integrate ψ(x) only up to x = B. When x = B, ψ(x) = ψ(B) is the amount
of the task that remains to be completed at time B under schedule the optimal schedule
S ∗ . We associate with this amount a yk , corresponding to the greedy schedule, where
k = min{ j : yj ≤ ψ(B) }. This can be seen in Figure 1, where x = B and y = ψ(B) are
shown as dotted lines, with yk being the first yj appearing below the dotted line y = ψ(B).
We first present an important fact. For any schedule S, any positive integer j ≤ d, and
any t >= 0,
f (Shti ) ≤ f (Gj ) + t · sj
(10)
This is a consequence of the monotonicity and submodularity of f , together with the fact
that the greedy algorithm always chooses the item with the best “bang for the buck”. It is
shown in Streeter and Golovin (2009) as Fact 1.
Using this fact, we have
∗
f (Shx
) ≤ f (Gj ) + xj sj = f (Gj ) +
ji

Rj
2

So, for j ≤ d we have
∗
ψ(xj ) = 1 − f (Shx
) ≥ 1 − f (Gj ) −
ji

Rj
Rj
= Rj −
2
2

and therefore
ψ(xj ) ≥ yj

(11)

Note that (11) holds for j > d as well, since xj = 0 by definition; thus, ψ(xj ) = ψ(0) = 1 ≥
yj .
24

Scenario Submodular Cover

1

ψ(x)

y1
y2
yd
yk

B

x

(a) The case where d < k. The area of the gray bars below yk is 0.

1

ψ(x)

y1
y2
y3
yk
y5
yd

B

x

(b) The case where d > k. The area of the gray bars below yk is
nonzero. Note that the bars below yk may extend past x = B.
Figure 1: Above yk , the gray bars fit entirely inside the area of integration of ψ − yk (the
area below the ψ(x) graph and above yk ). Below yk , the total area of the gray
bars is still less than the remaining area of integration for ψ (that is, the rectangle
bounded above by yk and on the right by the dotted line x = B)

25

Grammel Hellerstein Kletenik Lin

P
The cost of the greedy schedule is dj=1 Rj τj . The quantity Rj τj is the contribution of
action j to the cost of the greedy schedule. We can think of this quantity as charging τj
per unit of Rj . We can rewrite the contribution by instead dividing the charge per unit of
utility change, Rj − Rj+1 . That is, we can rewrite Rj τj as the product of Rj τj / (Rj − Rj+1 )
R
and Rj − Rj+1 . It follows from the definitions that Rj τj / (Rj − Rj+1 ) = sjj and therefore
1
xj (yj − yj+1 ) = Rj τj
4
Since cost(f, Gd ) =

Pd

j=1 Rj τj ,

(12)

we now have
d

X
1
cost(f, Gd ) =
xj (yj − yj+1 )
4

(13)

j=1

The lemma now follows immediately from the following claim:
RB
Pd
Claim 1
j=1 xj (yj − yj+1 ) ≤ x=0 ψ(x)dx.
To prove this claim, we note that for each j, we have a pair (xj , yj ). Figure 1 shows two
histograms (represented by gray bars). For any given j, we have a gray bar such that the
top of the bar is at yj , the bottom is at yj+1 , and the length of the bar is xj .
Proving the claim is equivalent to showing that the total area of the gray bars does
not exceed the integral of ψ(x) up to x = B. Combining (11) with the fact that ψ is
non-increasing, it follows that for a gray bar extending to a length of xj , the gray bar has a
height no more than yj and thus is below the graph of ψ. This allows us to conclude that
the gray bars fit entirely inside of the graph of ψ. However, since we are integrating ψ only
up to x = B, there may be some gray bars which, although they are within the graph of ψ,
fall outside of the area of integration of ψ. These are the values xj such that xj > B. We
note the following important fact:
Fact 1 For all j < k, xj ≤ B.
The justification for this fact is as follows: For any xj > B, we know that yj ≤ ψ(xj ) from
(11) and ψ(xj ) ≤ ψ(B) since ψ is nonincreasing. So, since xj > B implies that yj ≤ ψ(B),
we know that yj > ψ(B) implies that xj ≤ B. For all j < k, by the definition of k, we know
that yj > ψ(B), and thus xj ≤ B.
In order to show that the area of the histogram defined by the (xj , yj ) pairs is no larger
than the integral up to x = B of ψ(x), we will break the integral into two parts:
Z

B

Z

B

B

(ψ(x) − yk )dx +

ψ(x)dx =
x=0

Z

x=0

yk dx
x=0

and analyze each part. We note that the first part of the integral consists of the area above
the line y = yk . Above this line, the reasoning follows the same reasoning as in Streeter and
Golovin (2009): Due to (11), we see that each bar is contained entirely inside the graph of
ψ, and since j < k, the bar is entirely inside the area of integration.
The second part of the integral consists of the area below y = yk , where the bars are
still inside the graph of ψ, but may extend past x = B and thus fall outside the area of
26

Scenario Submodular Cover

integration. We must use different reasoning to show that the area of the bars below y = yk
do not exceed the area of ψ below yP= yk and
Pleft of x = B.
0
0
τj . Therefore, using (12), and the fact that
Let B = `(Gd ). We have B = j τj ≥
j≥k

Rj ≤ Rk for j ≥ k,
d
X

xj (yj − yj+1 ) =

j=k

d
X
1
j=k

1
τj Rj ≤ Rk B 0
4
4

(14)

This holds true even when d < k, as in this case the sum is simply 0.
Using this fact, combined with the fact that ψ(xj ) ≥ yj for j < d, we can prove the
claim. We have that
Z

d

B

X
1
1
yk dx = yk B = Rk B > Rk B 0 ≥
xj (yj − yj+1 )
2
4
x=0

(15)

j=k

where the last inequality follows from (14). If we look once again at Figure 1, we see that
for each j, we have a gray bar with area xj (yj − yj+1 ). From (11), we know that the gray
bars fit entirely inside ψ(x), and so the area of the gray bars above yk is not more than the
area under ψ(x) and above yk . That is,
Z

B

(ψ(x) − yk )dx ≥
x=0

k−1
X

xj (yj − yj+1 )

(16)

j=1

By using (15) and (16), we now have
Z B
Z
ψ(x) dx =
x=0

≥

B

Z

B

(ψ(x) − yk ) dx +

x=0
d
X

yk dx
x=0

xj (yj − yj+1 )

(17)

j=1

as desired, thus proving Claim 1. By proving Claim 1, we have therefore also proven Property 1, and thus Lemma 11.

Appendix B. O(k log n)-approximation for Scenario k-of-n function
evaluation
Let k ∈ {0, . . . , n} and let f : {0, 1}n → {0, 1} be the Boolean k-of-n function where
f (x) = 1 iff at least k bits of f are equal to 1. To determine the value of this f on an
unknown a ∈ {0, 1}n , we need to determine whether f has at least k ones, or at least
n − k + 1 zeros. There is an elegant polynomial-time exact algorithm solving the Stochastic
BFE problem for Boolean k-of-n functions (cf. Salloum (1979); Salloum and Breuer (1984);
Ben-Dov (1981); Chang et al. (1990)).
Here we consider the Scenario BFE problem for k-of-n functions. Following techniques
used in a reduction of Deshpande et al. (2014) for Stochastic BFE, we reduce this problem
27

Grammel Hellerstein Kletenik Lin

to a Scenario SC problem, through the construction of an appropriate utility function g for
the state set Γ = {0, 1}. We obtain g by combining two other functions g0 , and g1 , with
respective goal values n − k + 1 and k respectively, using the standard OR construction
described in Section 2. Function g1 : {0, 1, ∗}n → Z≥0 is such that for all b ∈ {0, 1, ∗}n ,
g1 (b) = min{k, |{i | bi = 1}|}. Similarly, g0 (b) = min{n − k + 1, |{i | bi = 0}|}. Combining
g0 and g1 , and their goal values using the OR construction yields the new function g :
{0, 1, ∗}n → Z≥0 such that for b ∈ {0, 1, ∗}n , g(b) = k(n − k + 1) − ((n − k + 1) − g0 (b))(k −
g1 (b)). The new goal value is Q = k(n − k + 1). For b ∈ {0, 1, ∗}n , g(b) = Q iff b either
contains at least (n − k + 1) 0’s or at least k 1’s, and thus determining the value of f on
initially unknown a is equivalent to achieving goal value for g.
We now lower bound the value of parameter ρ for this g. For b ∈ {0, 1, ∗}n where
g(b) < Q, and i such that bi = ∗, ∆g (b, i, 1) ≥ (n−k +1−g0 (b)) and ∆g (b, i, 0) ≥ (k −g1 (b)).
∆g (b,i,1)
∆g (b,i,0)
n−k+1−g0 (b)
k−g1 (b)
Thus Q−g(b)
≥ (n−k+1−g
= k−g11 (b) and Q−g(b)
≥ (n−k+1−g
≥ k1 .
0 (b))(k−g1 (b))
0 (b))(k−g1 (b))
The larger of these is at least k1 , and hence the value of ρ for g is at least k1 . It follows that
running Mixed Greedy on g with respect to the sample distribution, gives an O(k log n)
approximation algorithm for our Scenario Boolean k-of-n function evaluation problem. The
bound O(k log n) has no dependence on the sample size or on the weights. For constant k,
this bound is O(log n).
Our Scenario k-of-n function evaluation problem has some similarities to the Generalized
Min-Sum Set Cover problem, which has a constant-factor approximation algorithm (see,
e.g., Skutella and Williamson (2011)). However, in the Generalized Min-Sum Set Cover
problem, the goal is to find a non-adaptive strategy of minimum cost. Further, the sample
is unweighted, and the covering requirements are different for different assignments in the
input sample.

Appendix C. Adaptive Submodularity of gW
P
Proof of Lemma 3 Let w(b) = a∈S:ab w(a) be the sum of the weights of realizations
in the sample S that are extensions of b. Then, we can write hW (b) = W − w(b).
The OR construction gives us
gW (b) = QW − (Q − g(b))(W − hW (b))
By the properties of the standard OR construction, because g and hW are monotone
and submodular, so is gW .
Let b, b0 ∈ (Γ ∪ {∗})n such that b0  b, and i ∈ N where bi = b0i = ∗. To show
that gW is adaptive submodular with respect to distribution DS,w , we must show that
E[∆gW (b, i, γ)] ≥ E[∆gW (b0 , i, γ)] with respect to DS,w .
We start by finding ∆gW (b, i, γ) for any b ∈ (Γ ∪ {∗})n , γ ∈ Γ, and i ∈ N such that
bi = ∗:
∆gW (b, i, γ) = QW − (Q − g(bi←γ )) (W − hW (bi←γ ))
− QW + (Q − g(b)) (W − hW (b))
= QhW (bi←γ ) + W g(bi←γ ) − g(bi←γ )hW (bi←γ )
− QhW (b) − W g(b) + g(b)hW (b)
= Q∆hW (b, i, γ) + W ∆g(b, i, γ) + g(b)hW (b) − g(bi←γ )hW (bi←γ )
28

Scenario Submodular Cover

By adding and subtracting the same quantity, g(b)hW (bi←γ ), to the expression on the last
line, we get
∆gW (b, i, γ) = Q∆hW (b, i, γ) + W ∆g(b, i, γ) + g(b)hW (b) − g(bi←γ )hW (bi←γ )
+ g(b)hW (bi←γ ) − g(b)hW (bi←γ )
= Q∆hW (b, i, γ) + W ∆g(b, i, γ)
− g(b)(hW (bi←γ ) − h(b)) − hW (bi←γ )(g(bi←γ ) − g(b))
= Q∆hW (b, i, γ) + W ∆g(b, i, γ)
− ∆hW (b, i, γ)g(b) − ∆g(b, i, γ)hW (bi←γ )
= ∆hW (b, i, γ)(Q − g(b)) + ∆g(b, i, γ)(W − hW (bi←γ ))
We next recall that, by definition, hW (b) = W − w(b). Thus, we have that W − hW (bi←γ ) =
w(bi←γ ), and we can simplify further:
∆gW (b, i, γ) = ∆hW (b, i, γ)(Q − g(b)) + ∆g(b, i, γ)w(bi←γ )
We define for any partial realization d, the function Q̂(d) = Q − g(d) to represent the
amount of utility remaining to be achieved by d. Also, let Uγ = ∆g(b, i, γ) represent the
utility gained in g by observing state γ for item i in partial realization b. Let Wγ = w(bi←γ )
represent the weight of all realizations
in S consistent with bi←γ , referred to as the total
P
weight of state γ. Let W γ = γ 0 6=γ Wγ 0 represent the total weight of all states which are not
γ. It is clear that ∆hW (b, i, γ) = W γ . That is, the change in utility in hW (or conceptually,
the amount of weight eliminated ) is equal to the total weight of states which are not the
observed state, γ. We can now substitute these new values in the above equation and get:
∆gW (b, i, γ) = W γ Q̂(b) + Uγ Wγ
We now consider the calculation of the expected value of ∆gW . For a realization a ∈ Γn
w(bi←γ )
Wγ
drawn from DS,w , we have that P r[ai = γ | a  b] = w(b)
= w(b)
. Then, the expected
increase in utility is
X Wγ
E[∆gW (b, i, γ)] =
∆gW (b, i, γ)
w(b)
γ

X Wγ 
=
Q̂(b)W γ + Uγ Wγ
w(b)
γ
P
2
γ Wγ W γ Q̂(b) + Uγ Wγ
=
w(b)
P
2
γ Wγ W γ Q̂(b) + Uγ Wγ
P
=
γ Wγ
The last equality is true since Wγ = w(bi←γ ) and the sum of w(bi←γ ) for all γ is equal to
w(b).
We now consider the partial realization b0 . The expected value on partial realization b0
is analogous to the above expected value on b:
P
0
0
0
0
02
γ Wγ W γ Q̂(b ) + Uγ W γ
0
P
E[∆gW (b , i, γ)] =
0
γ Wγ
29

Grammel Hellerstein Kletenik Lin

P
0
where Wγ0 = w(b0i←γ ), W γ = γ 0 6=γ Wγ0 0 , and Uγ0 = ∆g(b0 , i, γ).
Next, let W = (Wγ1 , Wγ2 , . . . ) be the tuple containing all of the weights of the possible
states with respect to b, and let U = (Uγ1 , Uγ2 , . . . ) be the tuple containing all of the
Uγ values for each of the possible states. We also let W0 = (Wγ0 1 , Wγ0 2 , . . . ) and U0 =
(Uγ0 1 , Uγ0 2 , . . . ).
It follows from the submodularity of g that Q̂(b0 ) ≤ Q̂(b) and Uγ0 ≤ Uγ . Clearly Wγ0 ≤
Wγ . Finally, since g is monotone, and the maximum value of g on its domain is Q, Uγ ≤ Q̂(b)
and Uγ0 ≤ Q̂(b0 ).
Now let r = |Γ|. We will use wγ1 , wγ2 , . . . , wγr to represent variables for a new function
which we will define. Similarly, we will
P use uγ1 , uγ2 , . . . , uγr to represent variables of the
same function. We will also let wγ = γ 0 6=γ wγ 0 to simplify the definition of the function.
The wγ and uγ variables are analogous to the Wγ and Uγ in the expression for expected
value above. We now define our function f : R2|Γ|+1 → R such that
P
2
γ qw γ wγ + wγ uγ
P
f (wγ1 , . . . , wγr , uγ1 , . . . , uγr , q) =
γ wγ
Note that this function is analogous to the formula for expected value above. Specifically,
we consider the point (W0 , U0 , Q̂(b0 )) and the point (W, U, Q̂(b)). It should be noted that
f (W0 , U0 , Q̂(b0 )) = E[∆gW (b, i, γ)] and f (W, U, Q̂(b)) = E[∆gW (b0 , i, γ)]. Let P be the
path from the first point to the second point, which increases q continuously from Q̂(b0 ) to
Q̂(b), then increases each uγi continuously from Uγ0 i to Uγi for i = 1, 2, . . . , r, and finally
increases each wγi continuously from Wγ0 i to Wγi for i = 1, 2, . . . , r. We show that for every
point along the path P , the partial derivatives of f are non-negative, and therefore the value
of f is nondecreasing along the path. This proves that f (W, U, Q̂(b)) ≥ f (W0 , U0 , Q̂(b0 )).
This implies that E[∆gW (b, i, γ)] ≥ E[∆gW (b0 , i, γ)], and thus gW is adaptive submodular
with respect to distribution
DS,w .
P
We let K = γ wγ . Then, we start by taking the partial derivative with respect to q:
∂f
=
∂q

P

γ

(wγ wγ )
K

≥0

for all points on P since all weights are nonnegative and thus wγ ≥ 0.
We also examine the partial derivative with respect to each uγ . Given any γ, the partial
derivative is
wγ2
∂f
=
≥0
∂uγ
K
because K is positive since all weights are nonnegativeP
(i.e. wγ ≥ 0 for all wγ ).
Finally, for each wγ , we will use the fact that wγ = Pγ 0 6=γ wγ 0 . This means that for any
γ, we can express the sum of all weights as K = wγ + γ 0 6=γ wγ 0 = wγ + wγ . This fact is

30

Scenario Submodular Cover

used several times in the following. We have
!
P
wγ q + 2wγ uγ +
wγ 0 q K −
γ 0 6=γ
∂f
=
∂wγ
K2
(wγ q + 2wγ uγ + wγ q) (wγ + wγ ) −

!
i
Ph
2
wγ 0 wγ 0 q + wγ 0 uγ 0
γ0

P

w w q+
γ0

γ0

γ0

=

wγ20 uγ 0



K2

 P
2wγ wγ q + 2wγ2 uγ + 2w2γ q + 2wγ wγ uγ −
wγ 0 wγ 0 q + wγ20 uγ 0
γ0

=

K2

In the summation in the numerator, we look at the term for which γ 0 = γ and we can
simplify the numerator:

P 
wγ 0 wγ 0 q + wγ20 uγ 0
wγ wγ q + wγ2 uγ + 2w2γ q + 2wγ wγ uγ −
∂f
γ 0 6=γ
=
2
∂wγ
K
Then, we can find a lower bound on this expression for all points on P . We note that
initially, uγ ≤ q since Uγ ≤ Q̂(b0 ) for all γ. We first increase q continuously to Q̂(b). Then
we increase each uγ continuously from Uγ0 to Uγ . We also note that Uγ0 ≤ Q̂(b), and so
after we have increased each uγ we still have that uγ ≤ q. So at all points on the path we
have that uγ ≤ q, and we can replace in the summation in the numerator each uγ 0 by q to
produce our lower bound:

P
wγ wγ q + wγ2 uγ + 2w2γ q + 2wγ wγ uγ −
wγ 0 w γ 0 q + wγ 0 q
∂f
γ 0 6=γ
≥
2
∂wγ
K

P
2
2
wγ wγ q + wγ uγ + 2wγ q + 2wγ wγ uγ −
qwγ 0 wγ 0 + wγ 0
γ 0 6=γ

=

K2
wγ wγ q + wγ2 uγ + 2w2γ q + 2wγ wγ uγ − q

=
wγ w γ q +
=

wγ2 uγ

+

2w2γ q

P

wγ 0 K



γ 0 6=γ

K2

P
+ 2wγ wγ uγ − qK
wγ 0
γ 0 6=γ

K2

31

Grammel Hellerstein Kletenik Lin

Then we note that, by definition, wγ =

P

γ 0 6=γ

wγ 0 , and simplify further:

wγ wγ q + wγ2 uγ + 2w2γ q + 2wγ wγ uγ − qKwγ
=
K2
2
wγ q (wγ + wγ ) + wγ uγ + w2γ q + 2wγ wγ uγ − qKwγ
=
K2
2
2
wγ qW + wγ uγ + wγ q + 2wγ wγ uγ − qKwγ
=
K2
2
2
wγ uγ + wγ q + 2wγ wγ uγ
=
K2
≥0
for all points on P because wγ and uγ are nonnegative on P .
Thus, f is nondecreasing along path P , and gW is adaptive submodular with respect to
the distribution DS,w .

32

