Non-negative submodular stochastic probing via stochastic
contention resolution schemes
Marek Adamczyk

Department of Computer, Control, and Management Engineering, Sapienza University
of Rome, Italy, adamczyk@dis.uniroma1.it.
September 4, 2015

arXiv:1508.07771v3 [] 3 Sep 2015

1

∗1

Abstract
In a stochastic probing problem we are given a universe E, where each element e ∈ E is
active independently with probability pe ∈ [0, 1], and only a probe of e can tell us whether it
is active or not. On this universe we execute a process that one by one probes elements —
if a probed element is active, then we have to include it in the solution, which we gradually
construct. Throughout the process we need to obey inner constraints on the set of elements
taken into the solution, and outer constraints on the set of all probed elements. The objective
is to maximize a function of successfully probed elements.
This abstract model was presented by Gupta and Nagarajan (IPCO’13), and provides
a unified view of a number of problems. Adamczyk, Sviridenko, Ward (STACS’14) gave
better approximation for matroid environments and linear objectives. At the same time
this method was easily extendable to settings, where the objective function was monotone
submodular. However, the case of non-negative submodular function could not be handled
by previous techniques.
In this paper we address this problem, and our results are twofold. First, we adapt
the notion of contention resolution schemes of Chekuri, Vondrák, Zenklusen (SICOMP’14)
to show that we can optimize non-negative submodular functions in this setting with a
constant factor loss with respect to the deterministic setting. Second, we show a new contention resolution scheme for transversal matroids, which yields better approximations in the
stochastic probing setting than the previously known tools. The rounding procedure underlying the scheme can be of independent interest — Bansal, Gupta, Li, Mestre, Nagarajan,
Rudra (Algorithmica’12) gave two seemingly different algorithms for stochastic matching
and stochastic k-set packing problems with two different analyses, but we show that our
single technique can be used to analyze both their algorithms.

∗

Supported by the ERC StG project PAAl no. 259515.

1

1 INTRODUCTION

1

2

Introduction

Stochastic variants of optimization problems were considered already in 1950 [5, 10], but only
in recent years a significant attention was brought to approximation algorithms for stochastic
variants of combinatorial problems. In this paper we consider adaptive stochastic optimization
problems in the framework of Dean et al. [12] who presented a stochastic knapsack problem.
Since the work of Dean et al. a number of problems in this framework were introduced [9, 16,
17, 18, 2, 19, 11]. Gupta and Nagarajan [20] presented an abstract framework for a subclass
of adaptive stochastic problems giving a unified view for stochastic matching [9] and sequential
posted pricing [7]. Adamczyk et al. [1] generalized the framework by also considering monotone
submodular functions in the objective. In this paper we generalize the framework even further
by showing that also maximizing a non-negative submodular function can be considered in the
probing model. On the way we develop a randomized procedure for transversal matroids which
can be used to improve approximation for the k-set packing problem [4].
Below paper enhances the iterative randomized rounding for points from matroid polytopes
that was presented in [1]. The analysis from [1] does not easily carry over when the objective
submodular function is non-monotone. To handle non-monotone objectives we are making use
of contention resolution schemes introduced by Chekuri et al. [8]. Contention resolution schemes
in the context of stochastic probing already were used by Gupta and Nagarajan [20]. Recently,
Feldman et al. [14] presented online version of contention resolution schemes which, on top of
applications for online settings, yield good approximations for stochastic probing problem for
a broader set of constraints than before — most notably, for inner knapsack constraints and
deadlines.
Our paper fills the gaps between and merges results from basically four different paper [1,
8, 20, 13]. That is the reason why this paper comes with diverse contributions: we improve
the bound on measured greedy algorithm of Feldman et al. [13]; adjust contention resolution
schemes to stochastic probing setting in a way in which submodular optimization is be possible;
use iterative randomized rounding technique to develop contention resolution schemes; moreover,
we revisit the algorithms of Bansal et al. [4].
Below we present the necessary background.
The probing model
We describe the framework following [20]. We are given a universe E, where each element e ∈ E
is active with probability pe ∈ [0, 1] independently. The only way to find out if an element
is active, is to probe it. We call a probe successful if an element turns out to be active. On
universe E we execute an algorithm that probes the elements one-by-one. If an element is active,
the algorithm is forced to add it to the current solution. In this way, the algorithm gradually
constructs a solution consisting of active elements.
Here, we consider the case in which we are given constraints on both the elements probed and
the elements included in the solution. Formally, suppose that we are given
 two independence
the set
systems of downward-closed sets: an outer independence system E, I out restricting

in
of elements probed by the algorithm, and an inner independence system E, I , restricting
the set of elements taken by the algorithm. We denote by Qt the set of elements probed in the
first t steps of the algorithm, and by S t the subset of active elements from Qt . Then, S t is the
partial solution constructed by the first t steps of the algorithm. We require that at each time
t, Qt ∈ I out and S t ∈ I in . Thus, at each time t, the element e that we probe must satisfy both
Qt−1 ∪ {e} ∈ I out and S t−1 ∪ {e} ∈ I in . The goal is to maximize expected value E [f (S)] where
f : 2E → R≥0 and S is the set of all successfully probed elements.

We shall denote such a stochastic probing problem by E, p, I in , I out with function f stated
on the side, if needed.

3

1 INTRODUCTION

Submodular Optimization
A set function f : 2E 7→ R≥0 is submodular, if for any two subsets S, T ⊆ E we have f (S ∪ T ) +
f (S ∩ T ) ≤ f (S) + f (T ). Without loss of generality, we assume also that f (∅) = 0.
The multilinear extension F : [0, 1]E 7→ R≥0 of f , whose value at a point y ∈ [0, 1]E is given
by
X
Y Y
(1 − ye ) .
F (y) =
f (A) ·
ye
A⊆E

e∈A

e6∈A

Note that F (1A ) = f (A) for any set A ⊆ E, so F is an extension of f from discrete domain 2E
into a real domain [0, 1]E . The value F (y) can be interpreted as the expected value of f on a
random subset A ⊆ E that is constructed by taking each element e ∈ E with probability ye .
Contention Resolution Schemes
Consider a ground set of elements E and an down-closed family I ⊆ 2E of E’s subsets — we
call (E, I) an independence system. Let P (I) be the convex hull of characteristic vectors of sets
from I. Given x ∈ P (I) we define R (x) to be a random set in which every element e ∈ E is
included in R (x) with probability xe ; set R (x) defined like that is used frequently throughout
the paper.
Chekuri et al. [8] presented a framework of contention resolution schemes (CR schemes) that
allows to maximize non-negative submodular functions for various constraints. The following
definition and theorem come from [8].
Definition 1
Let (E, I) be independence system. For b, c ∈ [0, 1], a (b, c)-balanced CR scheme π for P (I) is a
randomized procedure that for every x ∈ b · P (I) and A ⊆ E, returns a random set πx (A) such
that:
1. always πx (A) ⊆ A ∩ supp (x) and πx (A) ∈ I,
2. P [e ∈ πx (A1 )] ≥ P [e ∈ πx (A2 )] whenever e ∈ A1 ⊆ A2 ,
3. for all e ∈ supp (x), P [ e ∈ πx (R (x))| e ∈ R (x)] ≥ c.
Theorem 1
Let (E, I) be an independence system. Let f : 2E → R be a non-negative submodular function
with multilinear relaxation F , and x be a point in b · P (I). Let π be a (b, c)-balanced CR scheme
for P (I), and let S = πx (R (x)). If f is monotone then E [f (S)] ≥ c · F (x) . Furthermore,
there is a function ηf : 2E → 2E that depends on f and can be evaluated in linear time, such
that even for f non-monotone E [f (ηf (S))] ≥ c · F (x) .
Function ηf (S) represents a pruning operation that removes from S some elements. To
prune a set S with pruning function ηf , an arbitrary ordering of the elements of E is fixed: for
simplicity of notation let E = {1, ..., |E|} which gives a natural ordering. Starting with S prun = ∅
the final set S prun = ηf (S) is constructed by going through all elements of E in the given order.
When considering an element e, S prun is replaced by S prun + e if f (S prun + e) − f (S prun ) ≥ 0.
Note that a pruning operation like that is not possible to execute in the probing model since
we commit to elements. We address this issue in Section 2, where we show how to perform
on-the-fly pruning.
Stochastic k-set packing
We are given n elements/columns, where each element e ∈ [n] has a random profit ve ∈ R+ , and
a random d-dimensional size Se ∈ {0, 1}d . The sizes are independent for different elements, but

1 INTRODUCTION

4

ve can be correlated with Se , and the coordinates of Se also might be correlated between each
other. Additionally, for each element e, there is a set Ce ⊆ [d] of at most k coordinates such that
each size vector Se takes positive values only in these coordinates, i.e., Se ⊆ Ce with probability
1. We are also given a capacity vector b ∈ Zd+ into which elements must be packed. We say that
column Se outcomes are monotone if for any possible realizations a, b ∈ {0, 1}d of Se , we have
a ≤ b or b ≤ a coordinate-wise. A strategy probes columns one by one, obeying the packing
constraints, and its goal is to maximize the expected outcome of taken columns. Bansal et al. [4]
gave a 2k-approximation algorithm for the problem, and a (k + 1)-approximation algorithm
when they assume that the outcomes of size vectors Se are monotone. The technique from [1]
allows to get a (k + 1)-approximation for the problem without the assumption of monotone
column outcomes.

1.1

Our contributions at a high level

There are two main contributions of the paper. First is Theorem 2 which implies that nonnegative submodular optimization in the probing model is possible if we are given CR schemes.
Our second contribution is the improved insight for transversal matroids in the context of
stochastic probing, captured in Theorem 4 and new analyses of algorithms from [4] for stochastic k-set packing and stochastic matching. It is based on the iterative randomized rounding
technique of [1].
1.1.1

Non-negative submodular optimization via CR schemes in the probing model

To obtain our results we extend the framework of CR schemes into the probing model, and we
define a stochastic contention resolution scheme (stoch-CR scheme). Define a polytope
o


 n
P I in , I out = x x ∈ P I out , p · x ∈ P I in , x ∈ [0, 1]E .

By act (S) we denote the subset of active elements of set S. Note that event e ∈ act (R (x))
means both that e ∈ R (x) and that e is active; this event has probability pe xe .
Definition 2

Let E, p, I in , I out be a stochastic probing
problem. For b, c ∈ [0, 1], a (b, c)-balanced stoch-CR


scheme π̄ for a polytope P I in , I out is a probing strategy that for every x ∈ b · P I in , I out and
A ⊆ E, obeys outer constraints I out , and the returned random set π̄x (A) satisfies the following:
1. π̄x (A) consists only of active elements,
2. π̄x (A) ⊆ A ∩ supp (x) and π̄x (A) ∈ I in ,
3. P [ e ∈ π̄x (R (x))| e ∈ act (R (x))] ≥ c,
4. P [e ∈ π̄x (A1 )] ≥ P [e ∈ π̄x (A2 )] whenever e ∈ A1 ⊆ A2 .
In Section 2 we present a mathematical program that models our problem. Solving the
program, getting x+ , and running the stoch-CR scheme π̄x+ on R (x+ ) constitute the algorithm
from the below Theorem.
Theorem 2

Consider a stochastic probing problem E, p, I in , I out , where we need to maximize a nonE
negative submodular
 function f : 2 7→ R≥0 . If there exists a (b, c)-balanced stoch-CR scheme
in
out
π̄ for P I , I  , then there exists a probing strategy whose expected outcome is at least
c b · e−b − o (1) · E [f (OP T )].

5

1 INTRODUCTION

 
 
−b k
-balanced scheme for
b, 1−eb

intersection of k matroids [8], and there exists a b, (1 − b)k -balanced ordered scheme for intersection of k matroids [7, 14]. For example when kin = kout = 1, Lemma 10 and the above
Theorem, after plugging appropriate number b, yield approximation of 0.13. See Section 2 for
discussion on other types of constraints.
To put this Theorem into perspective. There exists a

1.1.2

Optimization for transversal matroids

Stochastic probing on intersection of transversal matroids We improve upon the approximation described in the previous Section, if we assume the constraints are intersections of
transversal matroids. We do it by developing a new stoch-CR scheme. This scheme is direct in
the sense that we do not construct it by applying first a scheme for outer and then for inner
constraints, as in Lemma 10.
Lemma 3


There exists a b, 1+b·(kin1 +kout) -balanced stoch-CR scheme when constraints are intersections

of kin inner and kout outer transversal matroids.

For kin = kout = 1 the above Lemma together with Theorem 2 give approximation factor
of 0.15, so a modest improvement over 0.13, but it gets significantly better for larger values of
2
and we use Theorem 2 to conclude the
kin + kout . With k = kin + kout we plug b = √1+4k+1
following Theorem.
Theorem 4
For maximizing non-negative submodular function in the probing model with kin inner and kout
outer transversal matroids there exists an algorithm with approximation ratio of



1
1
q
1−Θ √
.
k
k + k + 14 + 12
There are further applications of the techniques used in Lemma 3.



1
Regular CR scheme for transversal matroids When kin = 0 this scheme yields b, 1+b·k

balanced CR scheme
for deterministic
setting. So far only a b, (1 − b)k -balanced ordered




k
-balanced scheme were known [8]; see section 2 for the defischeme and a b, 1 − eb /b
nition of ordered scheme. Our scheme can be seen as an improvement when one looks at the
1
2
1
.
maxb (b · c) — first one yields e(k+1)
, second e(k+1)
(for k big1 ), and we get k+1
Stochastic k-set packing and stochastic matching Here we want to argue that the
martingale-based analysis of the algorithm for transversal matroids can be of independent interest. In the bipartite stochastic matching problem [4] the inner constraints define bipartite matchings and outer constraints define general b-matchings — both are intersections of 2 transversal
matroids. Stochastic k-set packing problem does not belong to our framework, but we have
already defined it in previous subsection.
Bansal et al. [4] presented an algorithm for the k-set packing, and have proven that it yields
a (k + 1)-approximation but when assuming that the column outcomes are monotone. They also
presented a 3-approximation algorithm for the stochastic matching problem. Both algorithms
first choose a subset of elements: for k-set packing the elements are chosen independently,
and for stochastic matching the elements are chosen using a dependent rounding procedure of
1

The precise value is smaller than

1
k+1

starting k ≥ 4.

6

2 OPTIMIZATION VIA STOCH-CR SCHEMES

Gandhi et al. [15]. After that they probe elements in a random order. Bansal et al. [4] gave
two quite different analyses of the two algorithms, while we show how both algorithms can be
analyzed using our martingale-based technique for transversal matroids. First, we show that
their algorithm for set packing is in fact a (k + 1)-approximation even without the monotonicity
assumption (see Appendix F). Second, we also show that the our technique of analysis provides
a proof of 3-approximation of their algorithm for stochastic matching (see Appendix G).

2

Optimization via stoch-CR schemes

Mathematical program
Another extension of f studied in [6] is given by:


X

X
X
f + (y) = max
αA f (A)
αA ≤ yj , ∀A⊆E αA ≥ 0 .
αA ≤ 1, ∀j∈E


A⊆E

A⊆E

A:j∈A

Intuitively, the solution (αA ) A⊆E above represents the distribution over 2E that maximizes the
value E [f (A)] subject to the constraint that its marginal values satisfy P [i ∈ A] ≤ yi . The
value f + (y) is then the expected value of E [f (A)] under this distribution, while the value
of F (y) is the value of E [f (A)] under the particular distribution that places each element
i in A independently. This relaxation is important for our applications because the following
mathematical programming relaxation gives an upper bound on the expected value of the optimal
feasible strategy for the related stochastic probing problem:


maximize f + (x · p) x ∈ P I in , I out .
(1)

Lemma 5
Let OP T be the optimal feasible strategy for the stochastic probing problem in our general setting,
then E [f (OP T )] ≤ f + (x+ · p).
Proof of the following Lemma can be found in [1], and for sake of completeness we put it in
the Appendix C.
However, the framework of Chekuri et al. [8] uses multilinear relaxation F and not f + . The
Lemma below allows us to make a connection. Note that F (x) is exactly equal to E [F (R (x))],
i.e., it corresponds to sampling each point e ∈ E independently with probability xe , while
definition of f + (x) involves the best possible, most likely correlated, distribution of E’s subsets.
It follows immediately that for any point x we have f + (x) ≥ F (x), and therefore the following
Lemma states a stronger lower-bound for the measured greedy algorithm of Feldman et al. [13].
Details are presented in the next paragraph.
Lemma 6
Let b ∈ [0, 1], let f be a submodular function with multilinear extension F , and let P be any downward closed polytope. Then, the solution x ∈ [0, 1]E produced by the measured greedy algorithm
satisfies 1) x ∈ b · P, 2) F (x) ≥ b · e−b − o (1) · maxy∈P f + (y).
Stronger bound for measured continuous greedy

We now briefly review the measured continuous greedy algorithm of Feldman et al. [13]. The
algorithm runs for δ−1 discrete time steps, where δ is a suitably chosen, small constant. Let
y (t) be the algorithm’s current fractional
 time t, the
 algorithm selects
P solution at time t. At
vector I (t) ∈ P given by arg maxx∈P e∈E xe · F y (t) ∨ 1{e} − F (y (t)) (where ∨ denotes
element-wise maximum). Then, it sets ye (t + δ) = ye (t) + δIe (t) · (1 − ye (t)) and continues to
time t + δ.

7

2 OPTIMIZATION VIA STOCH-CR SCHEMES

The analysis of Feldman et al. shows that if, at every time step



F (y(t + δ)) − F (y(t)) ≥ δ · e−t · f (OP T ) − F (y(t)) − O n3 δ2 f (OP T ) ,
(2)


then we must have F (y(T )) ≥ T e−T − o (1) · f (OP T ). We note that, in fact, this portion of
their analysis works even if f (OP T ) is replaced by any constant value. Thus, in order to prove
our claim, it suffices to derive an analogue of (2) in which f (OP T ) is replaced by f + (x+ ), where
x+ = argmaxy∈P f + (y). The remainder of the proof then follows as in [13].
Lemma 7 below contains the required analogue of (2). Hence it implies Lemma 6. Proof of
below Lemma is placed in the Appendix A.
Lemma 7
For every time 0 ≤ t ≤ T



F (y(t + δ)) − F (y(t)) ≥ δ · e−t · f + (x+ ) − F (y(t)) − O(n3 δ2 ) · f + x+ .

Using stoch-CR schemes

The following Lemma is implied by Theorem 1 — it follows just from the fact that set act (R (x))
is distributed exactly as R (x · p).
Lemma 8
Let (E, p, I in , I out ) be a probing problem. Let f : 2E 7→ R≥0 be a non-negative
submodular

in , I out for b ∈ [0, 1]. Let π̄
function with multilinear relaxation F , and x be a point
in
b
·
P
I
x

be a (b, c)-balanced stoch-CR scheme for P I in , I out . Let π̄x (R (x)) be the output of the CR
scheme, and let ηf (π̄x (R (x))) be a pruned subset of π̄x (R (x)). It holds that
E [f (ηf (π̄x (R (x))))] ≥ c · F (x · p) .
However, we cannot apply yet the above Lemma to reason about a probing strategy, because
here the pruning ηf of S is done after the process. In the probing model we commit to an
element once we successfully probe it, and therefore we cannot do the pruning operation after
the execution of a stoch-CR scheme. However, since a probing strategy inherently includes
elements one-by-one, we can naturally add to any stoch-CR scheme the pruning operation done
on the fly. The idea is to simulate the probes of elements that would be rejected by the pruning
criterion. To simulate a probe of e means not to probe e and to toss a coin with probability
pe — in case of success to behave afterwards as if e was indeed taken into the solution, and
in case of failure to behave as if e was not taken. During the execution of a stoch-CR scheme
π̄x we construct two sets: S prun consists of elements successfully probed, and S virt consists of
elements whose simulation
was successful.

 If in a step we want to probe an element e such that
prun
virt
prun
virt
f S
+S
+e −f S
+S
< 0, then we simulate the probe of e and if successful
S virt ← S virt + e; otherwise we really probe e and S prun ← Sprun + e if successful. We can
see that at any step, it holds that S prun = ηf S prun + S virt . Also, the final random set
S prun + S virt is distributed
exactly as π̄x (R
(x)). Hence, the outcome of such a probing strategy

= E [f (ηf (π̄x (R (x))))] ≥ c · F (x · p) , where the
is E [f (S prun )] = E f ηf S prun + S virt
inequality comes from Lemma 8. Thus we have proven what follows.
Lemma 9
Let f ,x,π̄x be as in Lemma 8. There exists a probing strategy whose expected outcome is
E [f (ηf (π̄x (R (x))))] ≥ c · F (x · p).
Now we can finish the proof of Theorem 2. Consider the following algorithm. First, use
Lemma 6 to find a point x∗ such that


F (x∗ · p) ≥ b · e−b − o (1) ·
max
f + (x · p) .
x∈P(I in ,I out )

2 OPTIMIZATION VIA STOCH-CR SCHEMES

8

Second, run the probing strategy based on a stoch-CR scheme π̄x∗ as described in Lemma 9.
This yields, together with Lemma 5, that the outcome of such a probing strategy is


E [f (ηf (π̄x∗ (R (x∗ ))))] ≥ c · F (x∗ · p) ≥ c · b · e−b − o (1) ·
max
f + (x · p)
x∈P(I in ,I out )


≥ c · b · e−b − o (1) · E [f (OP T )] .

In [8] also an alternative approach than pruning was used. They defined a strict contention
resolution scheme where the approximation guarantee P [e ∈ πx (R (x)) |e ∈ R (x)] ≥ c holds with
equality rather than inequality. Since the pruning operation depends on an objective function,
resigning from it allows for the algorithm to be used in maximizing many submodular functions
at the same time. In our stochastic setting we can also skip the pruning operation if we have a
strict scheme. No proof of this fact is needed, since we can directly use an appropriate analog
of Lemma 8 (Theorem 4.1 from 1).
Stochastic probing for various constraints
Gupta and Nagarajan [20] introduced a notion of ordered CR scheme, for which there exists
a (possibly random) permutation σ of E, so that for each A the set πx (A) is the maximal
independent subset of I obtained by considering elements in the order of σ. Ordered scheme
are required to implement probing strategies, because of the commitment to the elements. CR
schemes exist for various types of constraints, e.g., matroids, sparse packing integer programs,
constant number of knapsacks, unsplittable flow on trees (UFP), k-systems (including intersection of k matroids, and k-matchoids). Ordered schemes exist for k-systems and UFP on trees.
See Theorem 4 in [20] for a listing with exact parameters.
The following Lemma is based on Lemma 1.6 from [8]. The proof basically carries over, the
only thing we have to do is to again incorporate probes’ simulations as in the proof of Lemma 9.
Proof of Lemma 10 is placed in Appendix C. Theorem 3.4 from [20] yields a similar result but
would imply a (b, cout + cin − 1)-balanced stoch-CR scheme. Thus the below Lemma can be
considered as a strengthening of Theorem 3.4 from [20], because an FKG inequality is used in
the proof instead of a union-bound.
Lemma 10

in , I out . Suppose we have a (b, c
Consider a probing
problem
E,
p,
I
CR-scheme
out )-balanced


in for P I in . Then there exists
π out for P I out , and a (b, cin )-balanced ordered CR scheme
π

a (b, cout · cin )-balanced stoch-CR scheme for P I in , I out .

In light of the above Lemma, one can question Definition 2 of a stoch CR-scheme — why do
we need to define it at all, if we can just be using two separate classic CR schemes π out , π in . The
reason is that there may exist stoch-CR schemes that are not convolutions of two deterministic
schemes, and that yield better approximations than corresponding convoluted ones. Such a
stoch-CR scheme is presented in Section 3.
In a recent paper, Feldman et al. [14] presented a variant of online contention resolution
schemes. They enriched the set of constraints possible to use in the stochastic probing problem
— previously inner knapsack constraints were not possible to incorporate, as well as deadlines
(element e can be taken only first de steps) for weighted settings. Their results can be extended
to monotone submodular settings by making use of a stronger bound for continuous greedy
algorithm [6] presented in [1]. The stronger bound for measured greedy algorithm — which works
for non-monotone functions — that we give in this paper can also be used in [14] enhancing
their result by the possibility of handling non-monotone functions as well.

3 STOCH-CR SCHEME FOR INTERSECTION OF TRANSVERSAL MATROIDS

3

9

Stoch-CR scheme for intersection of transversal matroids

In this section we prove Lemma 3. We assume we have only one inner matroid Min to keep the


1
.
presentation simple. Also, we shall present a 1, 21 -balanced CR scheme, instead of b, b+1

In the Appendix E we present a full scheme with arbitrary b, k in , and kout .

Our stoch-CR scheme on the input is given a point x such that p · x ∈ P Min and a set
A ⊆ E, and on the output it returns set π̄x (A). The procedure is divided in two phases. First,
the preprocessing phase, depends only on the point x. Second, the random selection phase,
depends on the set A ⊆ E and the outcome of the preprocessing phase.

Matroid properties

Let Min = E, I in . We know [21] that the convex hull of {1A |A ∈ I }, i.e., characteris
tic vectors of all P
independent sets of Min , is equivalent to the matroid polytope P Min =

of Min . Thus for
x ∈ RE
≥0 ∀A∈I in e∈A pe · xe ≤ rMin (A) , where rMin is the rank function
P
any x ∈ P Min in polynomial time we can find representation pP
·x = m
i=1 βi · 1Bi , where
β
=
1 . We shall call
B1 , . . . , Bm ∈ I and β1 , . . . , βm are non-negative weights such that m
i=1 i
in
sets B1 , . . . , Bm the support of p · x in M , and denote it by B.
In the remainder of the section we assume that we know the graph representation (E ∪ V, ⊆ E × V )
of the matroid described below. This assumption is quite natural and common, e.g., [3].
Definition 3
Consider bipartite graph (E ∪ V, ⊆ E × V ). Let I be a family of all subsets S of E such that
there exists a matching between S and V of size exactly |S|. Then M = (E, I) is a matroid,
called transversal matroid.
Preprocessing
In what follows we shall write superscripts indicating the time in which we are P
in the process.
We start by finding the support B 0 of vector p · x ∈ P Min , i.e., p · x = i βi · 1Bi0 . For
every two sets B, A ∈ B 0 we find a mapping φ0 [B, A] : B → A ∪ {⊥}, which we call transversal
mapping. This mapping will satisfy three properties.
Property 1
For each a ∈ A there is at most one b ∈ B for which φ0 [B, A] (b) = a.
Property 2
For b ∈ B \ A, if φ0 [B, A] (b) = ⊥, then A + b ∈ I, otherwise A − φ0 [B, A] (b) + b ∈ I.
Note that unlike in standard exchange properties of matroids, we do not require that
φ0 [B, A] (b) = b, if b ∈ A ∩ B. Property 3 will be presented in a moment. Once we find the
0
0
family φ0 of transversal mappings,
P for each element e ∈ E we choose one set among Bi : e ∈ Bi
with probability βi /pe xe ; since B 0 :e∈B 0 βi = pe xe this is properly defined. Denote by c (e)
i
i
t
the index of the chosen set, and call e-critical the set Bc(e)
for any t (note that c(e) is fixed
throughout the process). We nconcisely denote
o by C = (c (e))e∈E . For each
h indices of icritical sets

0 , B0
element e we define Γ0 (e) = f f 6= e ∧ φ0 Bc(f
c(e) (f ) = e — the blocking set of e. The
)
Lemma below follows from Property 1, and its proof is in the Appendix C.

Lemma 11

If p · x ∈
P Min , then for any element
e, it holds that
hP
i
EC,R(x)
f ∈Γ0 (e) pf · χ [f ∈ R (x)] ≤ 1, where the expectation is over R (x) and the choice of
critical sets C; here χ [E] is a 0-1 indicator of random event E.

3 STOCH-CR SCHEME FOR INTERSECTION OF TRANSVERSAL MATROIDS

10

Algorithm 1 Stoch-CR scheme π̄x (A)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

find support B 0 of p · x in Min and family φ0 ; choose critical sets C
remove from A all e : xe = 0; mark all e ∈ A as available
S←∅
while there are still available elements in A do
pick element e uniformly at random from A
if e is available then
probe e
if probe of e successful then
S ← S ∪ {e}
for each set Bit of support B t do
Bit ← Bit + e
call e unavailable
else simulate the probe of e
if probe or simulation was successful then
t
for each seth Bit of support
i B do
t , Bt
f ← φ Bc(e)
c(f ) (e)

t
t
if f 6= e then Bc(f
) ← Bc(f ) − f and call f unavailable
compute the family φt+1
for each i do Bit+1 ← Bit
t ← t + 1;
return S as π̄x (A)

Random selection procedure
The whole stoch-CR scheme is presented in Algorithm 1. During the algorithm we modify sets
of support B t after each step, but we keep the weights βi unchanged. We preserve an invariant
that each Bit from B t is an independent set of matroid Min . At the end of the algorithm the set
π̄x (A) belongs to every set Bit ∈ B t . Hence, the final set π̄x (A) is independent in every matroid.
Now we define Property 3 of transversal mappings. Suppose that in the first step we update
the support B 0 according to the for loop in line 15, and we obtain B 1 . Different support B 1
requires a different family of mappings φ1 , and so in step 2, the elements that can block e are
Γ1 (e). If it happens that Γ1 (e) 6= Γ0 (e), then we cannot show the monotonicity property of
stoch-CR scheme. However, we can require from the transversal mappings to keep the blocking
sets Γt (e) unchanged, as long as e is available. In the Appendix B we show how to find such a
family of transversal mappings φ0 and how to construct φt+1 given φt .
Property 3
Let φt be a family of transversal mappings for B t . Suppose we update the support B t and obtain
B t+1 . Then we can find a family φt+1 of transversal mappings such that Γt (e) = Γt+1 (e) for
any element e that is still available after step t.
Analysis
First, an explanation. We allow to pick in line 5 elements that we have once probed and simulate
their probe. This guarantees that the probability that an available element is blocked is equal
for every step. Otherwise, again, we would not be able to guarantee the monotonicity.
In the analysis we deploy martingale
theory. In particular Doob’s Stopping Theorem which

t
states that if a martingale Z t≥0 and stopping time τ are both “well-behaving”, then E [Z τ ] =
 
E Z 0 . In the Appendix D we put necessary definitions, statement of Doob’s Stopping Theorem,
and an explanation of why we can use this Theorem.

3 STOCH-CR SCHEME FOR INTERSECTION OF TRANSVERSAL MATROIDS

11

The random process executed in the while loop depends on the critical sets chosen in the
preprocessing phase. Therefore, when we analyze the random process we condition on the choice
of critical sets C.
We say e is available, if it is still possible to probe, i.e., it is not yet blocked, and it was not
yet probed. Define Xe = Je ∈ AK; in Iverson notation Jf alseK = 0 = 1 − JtrueK.
Let Yet for t = 0, 1, ..., be a random variable indicating if e is still available after step t.
Initially Ye0 = Xe . Let Pet be a random variable indicating if e was probed in one of steps
0, 1, ..., or t; we have Pe0 = 0 for all e. Variable Pet+1 − Pet indicates if e was probed at step t + 1.
Given the information F t about the process up to step t, the probability of this event is


Yt
E Pet+1 − Pet F t , C = e ,
|A|

1
because if element e is still available after step t (i.e., Yet = 1), then with probability |A|
we
t
choose it in line 5, and otherwise (i.e. Ye = 0) we cannot probe it.
Variable Yet − Yet+1 indicates whether element e stopped being available at step t + 1, i.e., we
Yet
), or some f ∈ Γt (e) has blocked
either have picked it in line 5 and probed (with probability |A|
Yet P
e in line 17 (with probability |A|
· f ∈Γt (e) pf Xf ). So in total

E Yet − Yet+1 F t , C =




and we can say that



t



E  Pet+1 − Pe · 1 +

X

f ∈Γt (e)

Yet

|A|



1 +


X

f ∈Γt (e)



pf Xf  ,


t+1

pf Xf  − Yet − Ye



F t , C  = 0.




P
is a martingale. Let
This means that the sequence
1 + f ∈Γt (e) pf Xf · Pet + Yet
t≥0

τ = min t Yet = 0 be the step in which edge e became unavailable. It is clear that τ is a
stopping time (definition in Appendix D). Thus from Doob’s Stopping Theorem we get that






X
X
Eτ  1 +
pf Xf  · Peτ + Yeτ C  = E  1 +
pf Xf  · Pe0 + Ye0 C  ,
f ∈Γ0 (e)

f ∈Γτ (e)

0 and Ye0 = Xe . We have Yeτ = 0, and expression
andP
this is equal to Xe , because Pe0 =P
1 + f ∈Γτ (e) pf Xf is in fact equal to 1 + f ∈Γ0 (e) pf Xf (Property 3 of the transversal mapping,
as e was available before step τ ), which depends solely on C and A. Hence


X
1 +
pf Xf  · Eτ [ Peτ | C] = Xe .
f ∈Γ0 (e)

Now just note that Eτ [ Peτ | C] is exactly the probability that e is probed, so we conclude that

,
X
P [e ∈ π̄x (A)| C] = pe · Eτ [ Peτ | C] = pe Xe 1 +
pf Xf  .
f ∈Γ0 (A)

0
Monotonicity Set
Pon A, but only on the vector p · x and C, so for
P Γ (e) does not depend
A1 ⊆ A2 we have f ∈Γ0 (A) pf · Jf ∈ A1 K ≤ f ∈Γ0 (A) pf · Jf ∈ A2 K.

3 STOCH-CR SCHEME FOR INTERSECTION OF TRANSVERSAL MATROIDS

12

Approximation guarantee In the identity
,
P [ e ∈ π̄x (A)| C] = pe Xe 1 +

X

f ∈Γ0 (A)



pf Xf 

we place random set R (x) instead of A; now Xf = χ [f ∈ R (x)] is a random variable. Let us
condition on e ∈ R (x), take expected value EC,R(x) [ ·| e ∈ R (x)], and apply Jensen’s inequality
to convex function x 7→ x1 to get:
P [ e ∈ π̄x (R (x))| e ∈ R (x)] = EC,R(x) [ P [e ∈ π̄x (R (x))| C, R (x)]| e ∈ R (x)]



,
X
= EC,R(x)  pe Xe 1 +
pf Xf  e ∈ R (x)
≥ pe
Since EC,R(x)

hP

f ∈Γ0 (e)

,



EC,R(x)  1 +

f ∈Γ0 (e)

X

f ∈Γ0 (e)



pf Xf e ∈ R (x) .

i
pf Xf e ∈ R (x) ≤ 1 from Lemma 11, we conclude that
P [ e ∈ π̄x (R (x))| e ∈ R (x)] ≥

pe
,
2

and therefore P [ e ∈ π̄x (R (x))| e ∈ act (R (x))] ≥ 12 , which is exactly Property 3 from the definition of stoch-CR scheme.

Acknowledgments
I thank Justin Ward for his help in proving Lemma 7, and also for valuable suggestions that
helped to improve the presentation of the paper.

REFERENCES

13

References
[1] Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on
matroids. In STACS, 2014.
[2] Arash Asadpour, Hamid Nazerzadeh, and Amin Saberi. Stochastic submodular maximization. In WINE, pages 477–489, 2008.
[3] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems,
and online mechanisms. In SODA, 2007.
[4] Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri
Rudra. When LP is the cure for your matching woes: Improved bounds for stochastic
matchings. Algorithmica, 63, 2012.
[5] E. M. L. Beale. Linear programming under uncertainty. Journal of the Royal Statistical
Society. Series B, 17:173–184, 1955.
[6] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a Submodular Set Function Subject to a Matroid Constraint. SIAM JoC, 40, 2011.
[7] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multiparameter mechanism design and sequential posted pricing. In STOC, 2010.
[8] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput.,
43(6):1831–1879, 2014.
[9] Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra.
Approximating matches made in heaven. In ICALP, 2009.
[10] G.B. Dantzig. Linear programming under uncertainty. Management Science, 1:197–206,
1955.
[11] Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for
stochastic packing problems. In SODA, pages 395–404, 2005.
[12] Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic
knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33, 2008.
[13] Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm
for submodular maximization. In FOCS, 2011.
[14] Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes.
CoRR, abs/1508.00142, 2015.
[15] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53, 2006.
[16] Michel X. Goemans and Jan Vondrák. Stochastic covering and adaptivity. In LATIN, pages
532–543, 2006.
[17] Sudipto Guha and Kamesh Munagala. Approximation algorithms for budgeted learning
problems. In STOC, pages 104–113, 2007.
[18] Sudipto Guha and Kamesh Munagala. Model-driven optimization using adaptive probes.
In SODA, pages 308–317, 2007.

REFERENCES

14

[19] Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, and R. Ravi. Approximation
algorithms for correlated knapsacks and non-martingale bandits. In FOCS, pages 827–836,
2011.
[20] Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications.
In IPCO, 2013.
[21] A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. 2003.

A STRONGER BOUND FOR MEASURED CONTINUOUS GREEDY

A

15

Stronger bound for measured continuous greedy

Recall, we need to prove Lemma 7. To do so, we shall require the following additional facts from
the analysis of [13].
Lemma 12 (Lemma 3.3 in [13])
ConsiderPtwo vectors x, x′ ∈ [0, 1]E , such that for every e ∈ E, |xe − x′e | ≤ δ. Then, F (x′ ) −
F (x) ≥ e∈E (x′e − xe ) · ∂e F (x) − O n3 δ2 · f (OP T ).

Lemma 13 (Lemma 3.5 in [13])
Consider a vector x ∈ [0, 1] E . Assuming xe ≤ a for every e ∈ E, then for every set S ⊆ E,
F (x ∨ 1S ) ≥ (1 − a)f (S).
Lemma 14 (Lemma 3.6 in [13])
For every time 0 ≤ t ≤ T and element e ∈ E, ye (t) ≤ 1 − (1 − δ) t/δ ≤ 1 − exp (−t) + O (δ).
Lemma 7. For every time 0 ≤ t ≤ T :

F (y(t + δ)) − F (y(t)) ≥ δ · e−t · f + (x+ ) − F (y(t)) − O(n3 δ2 ) · f + (x+ ).

Proof. Applying Lemma 12 to the solutions y(t + δ) and y(t), we have
F (y(t + δ)) − F (y(t))
X

δ · Ie (t) (1 − y(t)) · ∂j F (y(t)) − O n3 δ2 ) · f (OP T )
≥

(3)

e∈E

=

X

e∈E

=

X

e∈E

≥

X

e∈E

δ · Ie (t) (1 − y(t)) ·

F (y(t) ∨ 1j ) − F (y(t))
− O(n3 δ2 ) · f (OP T )
1 − y(t)

δ · Ie (t) · [F (y(t) ∨ 1j ) − F (y(t))] − O(n3 δ2 ) · f (OP T )
3 2
δ · x+
e [F (y(t) ∨ 1j ) − F (y(t))] − O(n δ ) · f (OP T )

(4)

where the last inequality follows P
from our choice of I(t).
P
+
+
Moreover,
we have f (x ) = A⊆E αA f (A) for some set of values αA satisfying A⊆E αA =
P
1 and A⊆E:e∈A αA = x+
e . Thus,
X

e∈E

x+
e [F (y(t) ∨ 1j ) − F (y(t))] =
≥

X

A⊆E

X

A⊆E

αA

X

j∈A

αA [F (y(t) ∨ 1A ) − F (y(t))] ≥

[F (y(t) ∨ 1j ) − F (y(t))]

X

A⊆E



αA (e−t − O(δ)) · f (A) − F (y(t))

= (e−t − O(δ)) · f + (x+ ) − F (y(t)).

where the first inequality follows from the fact that F is concave in all positive directions,
and the second from Lemmas 13 and 14. Combining this with the inequality (4), and noting
f + (x+ ) ≥ f + (OP T ) = f (OP T ), we finally obtain F (y(t + δ)) − F (y(t)) ≥ δ ·
 −t that
+
e · f (x+ ) − F (y(t)) − O(n3 δ2 ) · f + (x+ ).

B

Transversal mappings

Recall the definition of a transversal matroid.

B TRANSVERSAL MAPPINGS

16

Definition 4
Consider a bipartite graph (E ∪ V, ⊆ E × V ). Let I be a family of all subsets S of E such that
there exists an injection from S to V . Then M = (E, I) is a matroid, called transversal matroid.
We assume we know the graph (E ∪ V, ⊆ E × V ) of the matroid.
Let B 0 be the initial support. Let A ∈ B 0 be an independent set. From the definition of the
transversal matroid, there exists an injection v A : A → V ; we shall say that a ∈ A is matched
to v A (a). There can be many such injections for a given set, but we initially pick one for every
A ∈ B 0 . When a set of the support will be changed we shall explicitly define an injection. In
fact, only for added elements we will define a new match, for all other elements they will be
matched all the time to the same vertex, as long as they are available.
For any two A, B ∈ B 0 we define the mapping φ0 [B, A] : B → A ∪ {⊥} as follows. Let
v A be the injection of A, and let v B be the injection of B. If there exists element a such that
v A (a) = v B (b), then we set φ0 [B, A] (b) = a; if not, we set φ0 [B, A] (b) =⊥.
Let us verify that such a definition satisfies first two properties.
Property 1. For each a ∈ A there is at most one b ∈ B for which φ0 [B, A] (b) = a.
This one is trivially satisfied because there can be at most one b ∈ B that according to v B
is matched to v A (a).

Property 2. For b ∈ B\A, if φ0 [B, A] (b) = ⊥, then A+b ∈ I, otherwise A−φ0 [B, A] (b)+b ∈ I.
Suppose φ0 [B, A] (b) = ⊥. It means that b is matched to v B (b) to 
which no element
a ∈ A is

matched to. Therefore when we add edge (b, v B (b)) to the injection a, v A (a) a∈A it is still
0
′
a proper injection, since b ∈
/ A, and so A + b ∈ I. Now suppose
the
 φ A[B, A]
 (b) = a 6=⊥. Now
′
set A changes to A − a + b and the underlying injection is a, v (a) a∈A\a′ ∪ {(b, v B (b))},
which is a valid injection since b ∈
/ A, and if so, then A − a′ + b is indeed an independent set.
So Property 2 also holds.

Now let us move to the most technically demanding property.
Property 3. Let φt be a family of transversal mappings for B t . Suppose we update the support
B t and obtain B t+1 . Then we can find a family φt+1 of transversal mappings such that Γt (a) =
Γt+1 (a) for any element a that is still available after step t.
Suppose that in step t we have chosen element c, and we update the support B t as described
in the for loop of the algorithm in line 15. First of all assume that c 6= a, otherwise a becomes
t
unavailable so there is nothing to prove. Let C t be the critical set of c and let v C (c) be the
t
vertex to which c is matched according to v C . Consider set B t ∈ B t and let us describe how c
t+1
affects B t+1 and injection v B .
t
t
t
Case 1, c ∈ B t : If it is c from B t that is matched to v C (c), i.e., v B (c) = v C (c), then we do
t
t
t
t+1
= v B . If v B (c) 6= v C (c), then let
not have to change anything, we set B t+1 := B t and v B
t
t
b1 be such that v B (b1 ) = v C (c). We remove b1 from B t , i.e., B t+1 := B t \ b1 (we do not have
t
t+1
to add c to B t+1 because it is already there). For every b3 ∈ B t+1 we set v B (b3 ) = v B (b3 ).
See Figure 1.

17

B TRANSVERSAL MAPPINGS

Ct

c

t

t

b1

v B (b1) = v C (c)

c

v B (c)

t

t

v C (c)
c

b3

vB

t+1

vB

t+1

(c)

b3
t

v B (b3)

Bt

B t+1

V

V
Bt

B t+1

Figure 1: Illustration of Case 1, c ∈ B t

(b3)

18

B TRANSVERSAL MAPPINGS
t

t

Case 2, c ∈
/ B t : Let b1 be such that v B (b1 ) = v C (c). We remove b1 from B t and
t
t+1
add c instead, i.e., B t+1 = B t − b1 + c. The injection is defined as: v B (c) = v C (c), and
t
t+1
v B (b3 ) = v B (b3 ) for b3 ∈ B t \ b1 . See Figure 2.
Ct

c

t

t

b1

v B (b1) = v C (c)

b2

v B (b2)

t

b3

c

vB

t+1

b2

vB

t+1

vB

t+1

(c)
(b2)

b3
t

v B (b3)

Bt

B t+1

V

V
Bt

B t+1

Figure 2: Illustration of Case 2, c ∈
/ Bt

(b3)

19

C OMITTED PROOFS
t+1

Given sets At+1
, B t+1 with
corresponding injections v A ,v B


t+1
t+1
before, i.e., φt+1 B t+1 , At+1 (b) = a, if v A (a)n= v B (b). h

t+1

we define mapping φt+1 as

i
o
t+1
t+1
(b) = a is equal to
, Bc(a)
Now we need to show that the set Γt+1 (a) = b b 6= a ∧ φ Bc(b)
n
h
i
o
t , Bt
Γt (a) = b b 6= a ∧ φ Bc(b)
(b)
=
a
, if a is still available.
c(a)

Consider again sets At+1 , B t+1 and suppose that At is the critical set of a and that B t
t
t
is the critical set of b. Suppose that both a, b are matched to vab = v A (a) = v B (b), i.e.,
t
b ∈ Γt (a). If it happened that in step t element c removed a and b, i.e., v C (c) = vab , then
t
elements a, b are blocked and not available, so there is nothing to prove here. If v C (c) 6= v,
then from the reasoning in Case 1 and 2, we know that a and
 b are still matched to vab , i.e.,
t+1
t+1
vab = v A (a) = v B (b). But if so, then φt+1 B t+1 , At+1 (b) = a, and b ∈ Γt+1 (a) still,
t
because At+1 , B t+1 remain critical sets of a, b. Conversely, if b is not matched to v A (a), i.e.,
t
t
/ Γt (a). But if c during the update does not block b, then b does not
v B (b) 6= v A (a), then b ∈
t+1
t+1
/ Γt+1 (a).
change its matched vertex so we still have v B (b) 6= v A (a), and still b ∈
Illustration is given in Figure 3.

Ct

c

b1

a1

c

a2

c

a2

b3

a3

b3

a3

b4

a4

b4

a4

Bt

c

At
V

B t+1
Bt

B t+1

At+1
V

Figure 3: Illustration of change in Γ. We have blocked b1 , and if b1 ∈ Γt (a1 ), then it does
not matter anyway, because we have also blocked a1 . Element c was matched (w.r.t. Bt ) to
the same vertex as a2 , but Bt is not the critical set of c, so c ∈
/ Γt (a2 ). Assume B t is a
t
t
t
t
critical set of b3 : we have φ [B , A ](b3 ) = a3 and so b3 ∈ Γ (a3 ); after the update we still have
φt+1 [B t+1 , At+1 ](b3 ) = a3 , so b3 ∈ Γt+1 (a3 ). Element a4 did not have any element b′ ∈ B t in
Γt (a4 ), so it does not have any b′ ∈ B t+1 in Γt+1 (a4 ) as well.

C

Omitted proofs

Lemma 5. Let OP T be the optimal feasible strategy for the stochastic probing problem in our
general setting, then E [f (OP T )] ≤ f + (x+ · p).
Proof. We construct a feasible solution x of the following program
n

o
in
k out
out
maximize f + (x · p) x · p ∈ ∩kj=1 P Min
,
,
x
∈
∩
P
M
j
j=1
j

by setting xe = P [OP T probes e]. First, we show that this is indeed a feasible solution. Since
OP T is a feasible strategy, the set of elements Q probedby any execution of OP T is always an
T out
independent set of each outer matroid Mout
= E, Ijout , i.e. Q ∈ kj=1 Ijout . Thus the vector
j

20

C OMITTED PROOFS

o
n
T out
E [1Q ] = x may be represented as a convex combination of vectors from 1A A ∈ kj=1 Ijout ,



and so x ∈ P Mout
for any j ∈ 1, . . . , kout . Analogously, the set of elements S that
j
T in
were successfully probed by OP T satisfy S ∈ kj=1 Ijin for every possible execution of OP T .
Hence, the vector E
[1S ] = x · p may be
as a convex combination of vectors from
n
 represented


Tkin in o
in
1A A ∈ j=1 Ij
and so x · p ∈ P Mj
for any j ∈ 1, . . . , kin . The value f + (x · p)
gives the maximum value of ES∼D [f (S)] over all distributions D satisfying PS∼D [e ∈ S] ≤ xe pe .
The solution S returned by OP T satisfies P [e ∈ S] = P [OPT probes e] pe = xe pe . Thus, OP T
defines one such distribution, and so we have E [f (OP T )] ≤ f + (x · p) ≤ f + (x+ · p).


Lemmah 11. If p · x ∈ P Min , then
i for any element e, it holds that
P
EC,R(x)
f ∈Γ0 (e) pf · χ [f ∈ R (x)] ≤ 1, where the expectation is over R (x) and the choice of
critical sets C; here χ [E] is a 0-1 indicator of random event E.
Proof. In what follows let us skip writing 0 in the superscript of bases Bi0 , mappings φ0 ,
and set Γ0 (e).
Let us condition for now
set Bc(e) of element e. For f to belong to Γ (e) it
 on the critical

has to be the case that φ Bc(f ) , Bc(e) (f ) = e. Therefore


X
X
X


pf · χ [f ∈ R (x)] =
pf · χ [f ∈ R (x)] · 
χ [Bi is f -critical] ,
f ∈Γ(e)
f ∈E\{e}
i:φ[Bi ,Bc(e) ](f )=e
and by changing the order of summation it is equal to
X
X
pf · χ [f ∈ R (x)] · χ [Bi is f -critical] .
i f ∈Bi \e:φ[Bi ,Bc(e) ](f )=e


Consider f such that f ∈ Bi \ e : φ Bi , Bc(e) (f ) = e. Since χ [f ∈ R(x)] and c (f ) (the index

critical set of f ) are independent, and E [χ [f ∈ R (x)]] = xf and P Bi is f -critical| Bc(e) =


P i = c (f )| Bc(e) = pfβ·xi f , we get that
h
h
i
i
βi
= βi ,
E pf · χ [f ∈ R (x)] · χ Bij is f -critical Bc(e) = pf xf ·
p f xf

and hence


X
E
pf · χ [f ∈ R (x)] Bc(e) 
f ∈Γ(e)

=

X
i

X

f ∈Bi \e:φ[Bi ,Bc(e) ](f )=e

βij

≤

X

βij

=

1,

i

where the inequality
 follows from the fact that for each Bi there can be at most one element
f ∈ Bi such that φ Bi , Bc(e) (f ) = e.



Lemma 10 Consider a probing
problem E, p, I in , I out . Suppose we have a (b, cout )-balanced


in for P I in . Then
CR-scheme π out for P I out , and a (b, cin )-balanced ordered CR scheme
π

there exists a (b, cout · cin )-balanced stoch-CR scheme for P I in , I out .

Proof. First let us recall a Lemma T
from [8].
T
Lemma [1.6 from [8]] Let I = i Ii and PI = i Pi .Q Suppose each PIi has a monotone
(b, ci )-balanced
CR scheme. Then PI has a monotone (b, i ci )-balanced CR scheme defined as
T
πx (A) = i πxi (A) for A ⊆ N, x ∈ bPI .

C OMITTED PROOFS

21

Suppose we have a CR scheme π out for P(I out ) and an ordered CR scheme π in for P(I in ).
We would like to define the stochastic contention resolution scheme for P I in , I out just as in
in (act (A)). However, we cannot just simply run
the Lemma above, i.e., as πx (A) = πxout (A) ∩ πp·x
in
out
πx on A, and then πp·x on A again, and take the intersection, because that does not constitute
a feasible probing strategy. Once again, we need to make use of simulated probes to get a
in (act (A)). How to
stoch-CR scheme that will have a probability distribution of πxout (A) ∩ πp·x
in to scan elements
implement such a strategy? We first run πxout (A) on the set A. Later we use πp·x
in
of A in the order given from the definition of an ordered scheme. If πx considers element e such
that e ∈ A \ πxout (A), then we simulate the probe of e; if the e ∈ πxout (A), then we just probe
it.

in
out
out
virt
Therefore, the CR-scheme πp·x works in fact on the set act πx (A) + (A \ πx (A))
, where
(A \ πxout (A))virt represents simulated probes of elements in A \ πxout (A). Assuming e ∈ πxout
 (A),
virt
out
out
have
it is easy to see that elements in act (A) and elements in act πx (A) + (A \ πx (A))
the same probability distribution. Therefore,


in
P e ∈ πp·x
(act (A)) =



in
(act πxout (A) ∪ (A \ πxout (A))virt ) πxout (A), e ∈ πxout (A) . (5)
P e ∈ πp·x

And the RHS corresponds to a second phase of a feasible probing strategy. Thus we have:

P [e ∈ πx (A)]


in
= P e ∈ πxout (A) ∩ πp·x
(πxout (A) ∪ (A \ πxout (A))virt )
h 

 

i
in
= Eπxout χ e ∈ πxout (A) · Eπp·x
χ e ∈ πp·x
(act πxout (A) ∪ (A \ πxout (A))virt ) πxout (A), e ∈ πxout (A) .
in

Now just note that



 
in
Eπp·x
(πxout (A) ∪ (A \ πxout (A))virt ) πxout (A), e ∈ πxout (A) =
χ e ∈ πp·x
in



in
P e ∈ πp·x
(act πxout (A) ∪ (A \ πxout (A))virt ) πxout (A), e ∈ πxout (A) =


in
P e ∈ πp·x
(act (A)) , (6)

from line (5), and so we can simplify the previous expression to
 



in
(act (A))
P [e ∈ πx (A)] = Eπxout χ e ∈ πxout (A) · P e ∈ πp·x
 



in
(act (A))
= Eπxout χ e ∈ πxout (A) · P e ∈ πp·x




in
= P e ∈ πxout (A) · P e ∈ πp·x
(act (A)) .

Now the analysis just follows the lines of Lemma 1.6 from [8]. We plug R(x) for A, and apply
expectation on R (x) conditioned on e ∈ R (x) to get:
 




in
ER(x) [P [e ∈ πx (R (x))] |e ∈ R (x)] = ER(x) P e ∈ πxout (R (x)) · P e ∈ πp·x
(act (R (x))) |e ∈ R (x) .

From the fact that both π out , π in are
 monotone, and inact (R (x)) is an increasing function of
R (x) we get that P e ∈ πxout (R (x)) and also P e ∈ πp·x
(act (R (x))) are increasing functions
of R (x). Thus applying FKG inequality gives us that
ER(x) [P [e ∈ πx (R (x))] |e ∈ R (x)]
 




in
=ER(x) P e ∈ πxout (R (x)) · P e ∈ πp·x
(act (R (x))) |e ∈ R (x)
 


 


in
≥ER(x) P e ∈ πxout (R (x)) |e ∈ R (x) · ER(x) P e ∈ πp·x
(act (R (x))) |e ∈ R (x)
 


in
≥b · cout · ER(x) P e ∈ πp·x
(act (R (x))) |e ∈ R (x) .

D MARTINGALE THEORY

22

Now applying also expectation on act (R (x)), we get finally
ER(x),act(R(x)) [P [e ∈ πx (R (x))] |e ∈ R (x)]
 


in
≥ cout · ER(x),act(R(x)) P e ∈ πp·x
(act (R (x))) |e ∈ R (x) ≥ pe · cout · cin . (7)

 

in (act (A)) we get the
Also, directly from equation P [e ∈ πx (A)] = P e ∈ πxout (A) · P e ∈ πp·x
in (act (·)) are monotone.

monotonicity of the stoch CR-scheme πx , since both πxout and πp·x

D

Martingale Theory

Definition 5
Let (Ω, F, P) be a probability space, where Ω is a sample space, F is a σ-algebra on Ω, and P is
a probability measure on (Ω, F). Sequence {Ft : t ≥ 0} is called a filtration if it is an increasing
family of sub-σ-algebras of F: F0 ⊆ F1 ⊆ . . . ⊆ F.
Intuitively speaking, when considering a stochastic process, σ-algebra Ft represents all information available to us right after making step t. In our case σ-algebra Ft contains all information
about each randomly chosen element to probe, about outcome of each probe, and about each
support update for every matroid, that happened before or at step t.
Definition 6
A process (Zt )t≥0 is called a martingale if for every t ≥ 0 all following conditions hold:
1. random variable Zt is Ft -measurable,
2. E [|Zt |] < ∞,
3. E [ Zt+1 | Ft ] = Xt .
Definition 7
Random variable τ : Ω 7→ {0, 1, . . .} is called a stopping time if {τ = t} ∈ Ft for every t ≥ 0.
Intuitively, τ represents a moment when an event happens. We have to be able to say
whether it happened at step t given only the information from steps 0, 1, 2, . . . , t. In our case we
define τ as the moment when element became unavailable, i.e., it was chosen to be probed or it
was blocked by other elements. It is clear that this is a stopping time according to the above
definition.
Theorem 15 (Doob’s Optional-Stopping Theorem)
Let (Zt )t≥0 be a martingale. Let τ be a stopping time such that τ has finite expectation, i.e.,
E[τ ] < ∞, and the conditional expectations of the absolute
value of the

 martingale increments
are bounded, i.e., there exists a constant c such that E |Zt+1 − Zt | Ft ≤ c for all t ≥ 0. If so,
then E [Zτ ] = E [Z0 ].
In our case E [τ ] ≤ |A|, because we just pick an element at random from A, so the expected
value of picking e to be probed is exactly |A|, and since 
it can be earlier blocked
 by other elements,
P
, and
we have E [τ ] ≤ |A|. Also the martingale we use is
1 + f ∈Γt (e) pf Xf · Pet + Yet
t≥0


P
since Pet , Yet ∈ {0, 1} then it means that for any t we have 1 + f ∈Γt (e) pf Xf · Pet + Yet ≤
|A| + 1, and so E [|Zt+1 − Zt | Ft ] ≤ |A| + 1. Therefore, we can use Doob’s Optional-Stopping
Theorem in our analysis.

23

D MARTINGALE THEORY

out
out
in
Algorithm 2 Stoch-CR scheme π̄x (A) for Min
1 , ..., Mk in inner matroids and M1 , ..., Mk out
in
out
outer matroids, and x ∈ b · P I , I
.

//Preprocessing:


2: find support B 0in[j] of 1b p · x ∈ P Min
for each Min
j
j ;


3: find support B 0out[j] of 1b x ∈ P Mout
for each Mout
j
j ;
1:

4:

5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

0
out
find family φ0in[j] for every Min
j ; find family φout[j] for every Mj ;
out for each Mout ;
choose critical sets Cjin for each Min
j and Cj
j
//Random selection phase:
remove from A all e : xe = 0; mark all e ∈ A as available; S ← ∅
while there are still available elements in A do
pick element e uniformly at random from A
if e is available then
probe e
if probe of e successful then
S ← S ∪ {e}
for each matroid Min
j do
t
for each set Bit of support Bin[j]
do
t
t
Bi ← Bi + e
call e unavailable
else simulate the probe of e
if probe or simulation was successful then
for each set Bit of support B t do

f ← φ Bctin (e) , Bctin (f ) (e)
j

22:

j

if f 6= e then Bctin (f ) ← Bctin (f ) − f and call f unavailable
j

j

23:
24:
25:
26:

for each matroid Mout
do
j
t
for each set Bi of support B tout[j] do
t
Bit ← B
hi + e
i
f ← φ Bctout (e) , Bctout (f ) (e)
j

27:

j

if f 6= e then Bctout (f ) ← Bctout(f ) − f and call f unavailable
j

t+1
compute families φt+1
in[j] , φout[j]
29:
t←t+1
30: return S as πx (A)

28:

j

24

E FULL PROOF OF LEMMA ??

E

Full proof of Lemma 3

The full scheme
 is presented
 on Figure 2. Let us concisely denote by C all the critical sets
in
chosen, i.e., C = Cj
× Cjout
. Transversal mappings φ (M)0 are found in exactly
in
out
j∈[k ]

j∈[k

]

the same manner as in the single matroid version.
There are two
respect
 to what was presented in the main body. First,
 main differences with 
1
in
in
since p · x ∈ b · P Mj , then b p · x ∈ P Mj , and the support B 0in[j] is found by decomposing
1
b p · x. Thus when element f chooses a

in[j]
in[j]
βi / 1b pf xf = b · βi / (pf xf ). This

critical set in matroid Min
j it chooses with probability

results in the following modification in Lemma 11. The
proof is completely analogous, so we skip it.
Lemma 16 

If 1b p · x ∈ P Min
j , then for any element e, it holds that
hP
i
EC in ,R(x)
p
·
χ
[f
∈
R
(x)]
≤ b, where the expectation is over R (x) and the choice
0
f ∈Γin[j] (e) f
j
of critical sets C.
Now we also need to deal with outer matroids. Again, the proof is completely analogous, so
we skip it.
Lemma 17


1
out
If b x ∈ P Mj , then for any element e, it holds that
hP
i
ECjout ,R(x)
f ∈Γ0
(e) χ [f ∈ R (x)] ≤ b, where the expectation is over R (x) and the choice of
out[j]

critical sets C.

Second. Let Yet for t = 0, 1, ..., be a random variable indicating if e is still available after
step t. Initially Ye0 = Xe . Let Pet be a random variable indicating, if e was probed in one
of steps 0, 1, ..., or t. In step t + 1 element e can be blocked if, for some j ∈ [k in ], we pick
element f ∈ Γtin[j] (e) and successfully probe it (or successfully simulate), or if we just pick
element f ∈ Γtout[j] (e), and probe f or simulate its probe, irregardless of the outcome. Let
S
S
Γtout (e) = j∈[kout] Γtout[j] (e) and let Γtin (e) = j∈[kin] Γtin[j] (e) \ Γtout (e) — this subtraction is
to not count an element twice, because if element f belongs to both Γtin[j] (e) and Γtout[j] (e),
then just probing f (or simulating its probe) automatically blocks e, irregardless of f ’s probe
(simulation) outcome. Hence, we do cannot account for the excessive pf Xf influence of f on e.
Therefore, the probability that e stops to be available at step t + 1 is equal to


Yt
Yt
E Yet − Yet+1 F t , C = e + e ·
|A| |A|

X

pf Xf +

f ∈Γtin (e)

Yet
·
|A|

X

Xf .

f ∈Γtout (e)



As in the single matroid case, the probability of probing e is just equal to E Pet+1 − Pet F t , C =
Yet
|A| .

Thus the martingale we use now in the analysis is


1 +

X

f ∈Γtin (e)

pf Xf +

X

f ∈Γtout (e)





Xf  · Pet + Yet 

.

t≥0

Let τ = min t Yet = 0 be the step in which edge e became unavailable. It is clear that τ is a
stopping time. Thus from Doob’s stopping theorem we get that


25

E FULL PROOF OF LEMMA ??



Eτ  1 +

X

pf Xf +

f ∈Γτin (e)

X

f ∈Γτout (e)





Xf  · Peτ + Yeτ C 


= E  1 +

X

X

pf Xf +

f ∈Γ0in (e)

f ∈Γ0out (e)





Xf  · Pe0 + Ye0 C  ,

And as before, since the transversal mappings are controlled per matroid, we have that Γtin (e) =
Γ0in (e) and Γtout (e) = Γ0out (e) for t ≤ τ . Thus

,
X
X
P [e ∈ π̄x (A)| C] = pe · Eτ [ Peτ | C] = pe Xe 1 +
pf Xf +
Xf  .
(8)
f ∈Γ0in (e)

f ∈Γ0out (e)

Monotonicity follows as before. The approximation guarantee similarly from Jensen.
We take random set R (x) instead of A; now Xf = χ [f ∈ R (x)] is a random variable. Let us
condition on e ∈ R (x), take expected value EC,R(x) [ ·| e ∈ R (x)] on both sides of 8, and apply
Jensen’s inequality to convex function x 7→ x1 to get:
P [ e ∈ π̄x (R (x))| e ∈ R (x)] = EC,R(x) [ P [ e ∈ π̄x (R (x))| C, R (x)]| e ∈ R (x)] =
.

h
i
P
P
1 + f ∈Γ0 (e) pf Xf + f ∈Γ0 (e) Xf e ∈ R (x)
= EC,R(x) pe Xe
in
i
h out P
.
P
≥ pe EC,R(x) 1 + f ∈Γ0 (e) pf Xf + f ∈Γ0 (e) Xf e ∈ R (x) .
out

in

Since




EC,R(x) 

from Lemma 16, and

X

f ∈Γ0in[j] (e)




EC,R(x) 



f ∈Γ0out[j] (e)

f ∈Γ0in (e)

X

≤ EC,R(x)  1 +


pf Xf e ∈ R (x) ≤ b

X

from Lemma 17, we conclude that

X
EC,R(x)  1 +
pf Xf +




X

X

f ∈Γ0out (e)

pf Xf +

j∈[k in ] f ∈Γ0in[j] (e)

≤1 +

X



j∈[k in ]

+


EC,R(x) 

X

j∈[k out ]

X


EC,R(x) 

≤ 1 + kin · b + kout · b.



Xf e ∈ R (x)
X

X

j∈[k out ] f ∈Γ0out[j] (e)



f ∈Γ0in[j] (e)




Xf e ∈ R (x) ≤ b


pf Xf e ∈ R (x)

X

f ∈Γ0out[j] (e)




Xf e ∈ R (x)




Xf e ∈ R (x)

26

F STOCHASTIC K-SET PACKING
And therefore
P [ e ∈ π̄x (R (x))| e ∈ R (x)] ≥

b (kin

pe
,
+ kout ) + 1

which yields
P [ e ∈ π̄x (R (x))| e ∈ act (R (x))] ≥

b (kin

1
,
+ kout ) + 1

which is exactly Property 3 from the definition of stoch-CR scheme. Lemma 3 follows.

F

Stochastic k-set packing

In this section we are showing a (k + 1)-approximation algorithm for Stochastic k-Set Packing.
We are given n elements/columns, where each item e ∈ E = [n] has a profit ve ∈ R+ ,
and a random d-dimensional size Se ∈ {0, 1}d . The sizes are independent for different items.
Additionally, for each item e, there is a set Ce of at most k coordinates such that each size vector
Se takes positive values only in these coordinates, i.e., Se ⊆ Ce with probability 1. We are also
given a capacity vector b ∈ Zd+ into which items must be packed. We assume that ve is a random
variable that can be correlated with Se . The coordinates of Se also might be correlated between
each other.
Important thing to notice is that in this setting, unlike in the previous ones, here when we
probe an element, there is no success/failure outcome. The size Se of an element e materializes,
and the reward ve is just drawn.
Let pje = E [Se (j)] be the expected size of the j coordinate of column e. The following is an
LP that models the problem. Here U (c) denotes a uniform matroid of rank c.
max

n
X
e=1

s.t.

E [ve ] · xe

pj · x ∈ P (U (bj ))
xe ∈ [0, 1]

(LP-k-set)
∀j ∈ [d]

∀e ∈ [n] .

Where, as usual, xe stands for P [OP T probes column e]. We are going to present a probing
xe
. From
strategy in which for every element e probability that we will probe e will be at least k+1
this the Theorem will follow.
The algorithm is presented on Figure 3.
Constraint for row j is in fact given be a uniform matroid in which we can take
P at most
bj elements from subset {e |j ∈ Ce } ⊆ E. Therefore, we can decompose pj · x = l βlj · Blj,0 .
Uniform matroid is a transversal matroid, so we use the transversal mapping φ0j between sets

B j,0 , also let C = C j j∈[d] be the vector indicating the critical sets. We define in the same way

as we did already in Lemma 3, the sets Γ0j (e) of blocking elements, i.e.,
o
n
Γ0j (e) = f f 6= e ∧ φ0j [Bc0j (f ) , Bc0j (e) ] .

As before, let us from now on condition on C. Let us analyze the impact of f ∈ Γtj (e) on
e. Element f ∈ Γtj (e) blocks e when f is chosen and Sf (j) = 1. However, right now f can
belong to Γtj (e) for many j ∈ Ce . Therefore if f is chosen in line 9 of the Algorithm 3, then the
hW
i
probability that f blocks e is equal to P
C
.
(S
(j)
=
1)
t
f
j:f ∈Γ (e)
j

Let us now repeat the steps of Lemma 1. Let Xe = χ [e ∈ R (x)]. Let Yet for t = 0, 1, ..., be
a random variable indicating if e is still available after step t. Initially Ye0 = Xe . Let Pet be a
random variable indicating, if e was probed in one of steps 0, 1, ..., or t; we have Pe0 = 0 for all
e.

F STOCHASTIC K-SET PACKING

Algorithm 3 Algorithm for stochastic k-set packing
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

//Preprocessing:
for each j ∈ [d] do
find support Bj0 of pj · x in P (U (bj ))
family φ0j

critical sets C = C j j∈[d]
//Rounding:
let A ← R (x); mark all e ∈ A as available; S ← ∅
while there are still available elements in A do
pick element e uniformly at random from A
if e is available then
probe e
S ←S+e
for each j ∈ Ce such that Se (j) = 1 do
for each set Bij,t of support B j,t do
Bij,t ← Bij,t + e
call e unavailable
else simulate the probe of e
for each j ∈ Ce such that Se (j) = 1 (whether we probe or simulate) do
j,t
for each seth Bij,t of support
i B do
j,t
f ← φ Bcj,t
j (e) , Bcj (f ) (e)

j,t
if f 6= e then Bcj,t
j (f ) ← Bcj (f ) − f and call f unavailable

compute the family φt+1
j

for each i do Bij,t+1 ← Bij,t
24:
t←t+1
25: return S
23:

27

28

F STOCHASTIC K-SET PACKING

Variable Pet+1 − Pet indicates if e was probed at step t + 1. Given the information F t about


Yet
, because if
the process up to step t, the probability of this event is E Pet+1 − Pet F t , C = |A|
1
t
element e is still available after step t (i.e., Ye = 1), then with probability |A| we choose it in
line 9, and otherwise (i.e. Yet = 0) we cannot probe it.
Variable Yet − Yet+1 indicates whether element e stopped being available at step t + 1. For
this to happen we need to pick f ∈ Γtj (0) and the probe (or simulation) of f needs to result in
a vector Sf such that Sf (j) = 1. However, as already noted, there can be many j for which
f ∈ Γtj (0). Therefore, probability that e stops being available in step t + 1 is equal to


E Yet − Yet+1 F t , C =

Yet
|A|

+

Yet
|A|

·

X
f




Xf · P 



_

j:f ∈Γtj (e)


(Sf (j) = 1) C  .

Here we stress the condition on C because sets Γtj are constructed given the choice of critical
sets. Again we can reason that




_
X




(Sf (j) = 1) C  · Pet + Yet 
Xf · P 
1 +
j:f ∈Γtj (e)

f

t≥0


is a martingale. Let τ = min t Yet = 0 be the step in which edge e became unavailable. It is
clear that τ is a stopping time. Thus from Doob’s Stopping Theorem we get that



Eτ  1 +

X
f



Xf · P 

_

j:f ∈Γτj (e)







(Sf (j) = 1) C  · Peτ + Yeτ C 


X


= Eτ  1 +
Xf · P 
f

_

j:f ∈Γ0j (e)







(Sf (j) = 1) C  · Pe0 + Ye0 C  = Xe .

We argue again using the properties of transversal mapping φtj that we have Γτj (e) = Γ0j (e) for
each j ∈ Ce , since e was available before step τ . And if so, then




X
_




Eτ  1 +
(Sf (j) = 1) C  · Peτ + Yeτ C  = Xe
Xf · P 
f

j:f ∈Γ0j (e)


hW
i
P
and since 1 + f Xf · P
(S
(j)
=
1)
C
is just a number depending on C, we can
0
f
j:f ∈Γj (e)
say that



X


 _
(Sf (j) = 1) C  · Eτ [ Peτ | C] = Xe .
Xf · P 
1 +
f

j:f ∈Γ0j (e)

Note that Eτ [ Peτ | C] = P [ e is probed| C], and conclude that


,
X

 _
P [ e is probed| C] = Xe 1 +
Xf · P 
f

j:f ∈Γ0j (e)




(Sf (j) = 1) C  .

G

STOCHASTIC MATCHING AND HANDLING NEGATIVE CORRELATION

29

At this point we reason as follows:

X
f




Xf · P 

≤

X

=

X

=

X

f

f

Xf ·

Xf ·



_

j:f ∈Γ0j (e)


(Sf (j) = 1) C 

X

P [ Sf (j) = 1| C]

X

pjf

j:f ∈Γ0j (e)

j:f ∈Γ0j (e)

X

pjf Xf ,

j∈Ce f ∈Γ0j (e)

where inequality just follows simply from the union-bound. Then we have an identity since event
(Sf (j) = 1) is independent of C and its probability is just equal to pjf . Later we just change the
order of summation. Therefore we have shown that


,
X X j


pf Xf  .
P [ e is probed| C] ≥ Xe 1 +
j∈Ce f ∈Γ0j (e)

We apply expectation EC,R(x) [ ·| e ∈ R (x)] to both sides, use Jensen’s inequality to get



,

X X j

pf Xf e ∈ R (x) .
P [ e is probed| e ∈ R (x)] ≥ 1 1 + EC,R(x) 
j∈Ce f ∈Γ0j (e)

Now we can say that



X X j
pf Xf e ∈ R (x)
EC,R(x) 
j∈Ce f ∈Γ0j (e)

=

X

j∈Ce





X

 X j
1 = |Ce | ≤ k,
pf Xf e ∈ R (x) ≤
EC,R(x) 
f ∈Γ0j (e)

j∈Ce

hP
i
j
where the last inequality EC,R(x)
f ∈Γ0j (e) pf Xf e ∈ R (x) ≤ 1 for each j comes from Lemma 11.
Hence
1
P [ e is probed| e ∈ R (x)] ≥
,
1+k
which gives
P [e is probed] = P [e ∈ R (x)] · P [ e is probed| e ∈ R (x)] ≥

xe
1+k

as desired.

G

Stochastic Matching and handling negative correlation

In the Stochastic Matching problem we are given an undirected graph G = (V, E). Each edge
e ∈ E is assigned a probability pe ∈ (0, 1] and a weight we > 0, and each node v ∈ V is assigned

G

STOCHASTIC MATCHING AND HANDLING NEGATIVE CORRELATION

30

a patience tv ∈ N+ . Each time an edge is probed and it turns out to be present with probability
pe , in which case it is (irrevocably) included in the matching we gradually construct and it gives
profit we . Therefore the inner constraints are given by intersection of two partition matroids.
We can probe at most tu edges that are incident to node u — these are outer constraints which
also can be described by intersection of two partition matroids. Our goal is to maximize the
expected weight of the constructed matching.
Let us consider the bipartite case where V = (A ∪ B) and E ⊆ A × B. In this case Bansal et
al. [4] provided an LP-based 3-approximation. We shall also obtain this approximation factor.
Here we present a variant of our scheme from Lemma 3 that does not use transversal mappings,
because in this case they are trivial. Moreover, previously we required the input of the stoch-CR
scheme to be a set of elements sampled independently, i.e., R (x). Now we shall apply the ideas
from Lemma 3, but we use it on a set of edges that are negatively correlated. Such a set is
returned by the algorithm of Gandhi et al. [15]. Also, since the objective is linear, and not
submodular, we do not have to take care of the monotonicity of the scheme, and therefore we
do not draw edges with repetitions. In fact we just scan rounded edges according to a random
permutation, and therefore the below algorithm is the same that was presented by Bansal et
al. [4]. Thus what follows is an alternative analysis of the algorithm from [4].
Consider the following LP for stochastic matching problem:
max

X

(9)

we pe xe

e

X

e∈δ(v)

X

e∈δ(v)

p e xe ≤ 1

∀v ∈ V

(10)

xe ≤ t v

∀v ∈ V

(11)

∀e ∈ E.

(12)

0 ≤ xe ≤ 1

Suppose that (xe )e∈E is the optimal solution to this LP. We round the
with dependent
 solution

rounding of Gandhi et al. [15]; we call the algorithm GKPS. Let X̂e
be the rounded
e∈E
n
o
solution, and denote Ê = e ∈ E X̂e = 1 . From the definition of dependent rounding we
know that:
h
i
1. (Marginal distribution) P X̂e = 1 = xe ;
2. (Degree preservation) For any v ∈ V it holds that


X
X
xe 
X̂e ≤ 
 ≤ tv ;



e∈δ(v)
e∈δ(v)

3. (Negative correlation) For any v ∈ V and any subset S ⊆ δ (v) of edges incident to v it
holds that:
"
#

i
^
Y h
∀b∈{0,1} P
P X̂e = b .
X̂e = b ≤
e∈S

e∈S

Negative correlation property and constraint (10) imply that




X
X
X
E
pf X̂f e ∈ Ê  ≤ E 
pf X̂f  =
pf xf ≤ 2 − 2pe xe .
f ∈δ(e)

f ∈δ(e)

f ∈δ(e)

(13)

G

STOCHASTIC MATCHING AND HANDLING NEGATIVE CORRELATION

31

Algorithm 4 Algorithm for Stochastic Matching
1: Solve the LP; let x an optimal solution;
o
n
2: let X̂ ∈ {0, 1}E be a solution rounded using GKPS; let Ê = e X̂e = 1 ; call every e ∈ Ê
safe
3: while there are still safe elements in Ê do
4:
pick element e uniformly at random from safe elements of Ê
5:
probe e
6:
if probe successful then
7:
S ← S ∪ {e}
8:
call every f ∈ Ê ∩ δ (e) blocked
9: return S
 
Given the solution X̂e

e∈E

we execute the selection algorithm presented on Figure 4. Because

of the Degree preservation property we will not exceed the patience of any vertex. We say that
an edge e is safe if no other edge adjacent to e was already successfully probed; otherwise edge
is blocked. Initially all edges are safe.
The expected outcome of our algorithm is
X
e

P [e probed] · pe · we =

i
h
i
X h
P X̂e = 1 · P e probed| X̂e = 1 · pe · we
e

=

X
e

h
i
we pe xe · P e probed| X̂e = 1 ,

h

i
and we shall show that P e probed| X̂e = 1 ≥ 13 for any edge e, which will imply 1/3-approximation
of the algorithm.
From now let us condition that we know the set of edges Ê and we know that X̂e = 1.
Consider a random variable Yet which indicates if edge e is still in the graph after step t. We
consider variable Yft for any edge f ∈ E. Initially we have Yf0 = 1 for any f ∈ Ê, and Yf0 = 0
for f ∈
/ Ê. Let variable Pet denote if edge e was probed in one of steps 0, 1, ..., t; we have Pe0 = 0.
Let Σt be the number of edges that are left after t steps. Variable Pet+1 − Pet indicates
whether edge e was probed in step
F t about the process up to step
h t + 1. Given the information
i
t
t, probability of this event is E Pet+1 − Pet F t , Ê, X̂e = 1 = YΣet , i.e., if edge e still exists in the
graph after step t (i.e. Yet = 1), then the probability is Σ1t , otherwise it is 0.
Variable Yet − Yet+1 indicates whether
edge e was blockedifrom the graph in step t +1. Given
h
P
t
t
t
t
F , probability of this event is E Ye − Yet+1 F t , Ê, X̂e = 1 = YΣet ·
f ∈δ(e) pf Yf + 1 .
It is immediate to note that Yft ≤ X̂f for any edge f , and that Pet+1 − Pet is always nonnegative. Hence



X


pf X̂f + 1 · Pet+1 − Pet − Yet − Yet+1 F t , Ê, X̂e = 1
E 
f ∈δ(e)



≥E  

X

f ∈δ(e)







pf Yft + 1 · Pet+1 − Pet − Yet − Yet+1 F t , Ê, X̂e = 1 = 0,

which means that the sequence



X

f ∈δ(e)





pf X̂f + 1 · Pet − 1 − Yet 

t≥0

G

32

STOCHASTIC MATCHING AND HANDLING NEGATIVE CORRELATION

is a super-martingale.

Let τ = min t Yet = 0 be the step in which edge e was either blocked or probed. It is clear
that τ is a stopping time. Thus
from Doob’s

 Stopping Theorem —
 this
 time in the variant for
super-martingales, i.e., if E Z t+1 − Z t F t ≥ 0 , then E [Z τ ] ≥ E Z 0 — we get that


Eτ  

X

f ∈δ(e)





pf X̂f + 1 · Peτ − (1 − Yeτ ) Ê, X̂e = 1


≥ E 

X

f ∈δ(e)




0

pf X̂f + 1 · Pe0 − 1 − Ye



Ê, X̂e = 1 ,

where the expectation above is over the random variable τ only. Since Pe0 = 0,Ye0 = 1,Yeτ = 0
the above inequality implies that



X
Eτ  
pf X̂f + 1 · Peτ Ê, X̂e = 1 ≥ 1.
f ∈δ(e)

Since we condition all the time on Ê and X̂e = 1 we can write that


h
i
X

pf X̂f + 1 · Eτ Peτ | Ê, X̂e = 1 ≥ 1.
f ∈δ(e)

h
i
h
i
Let us notice that Eτ Peτ | Ê, X̂e = 1 is exactly equal to P e probed| Ê, X̂e = 1 . Thus we can
write that
h
i
1
.
P e probed| Ê, X̂e = 1 ≥ P
f ∈δ(e) pf X̂f + 1
Now we can apply to both sides of the above inequality expectation over Ê but still conditioned
on X̂e = 1:
h
i
h h
i
i
P e probed| X̂e = 1 = EÊ P e probed| Ê, X̂e = 1 X̂e = 1
"
≥ EÊ

1
P

f ∈δ(e) pf X̂f

+1

and from Jensen’s inequality, and the fact that x 7→ x1 is convex, we get that
"
#
1
1
hP
i.
EÊ P
X̂e = 1 ≥
X̂
=
1
p
X̂
+
1
EÊ
f ∈δ(e) pf X̂f + 1
e
f ∈δ(e) f f

From inequality (13) we get EÊ
2xe pe ≤ 3 and we conclude that

hP

#

X̂e = 1 ,

i
hP
i
p
X̂
+
1
X̂
=
1
≤
E
p
X̂
+
1
≤ 3−
e
f
f
f
f
f ∈δ(e)
f ∈δ(e)
Ê

h
i 1
P e probed| X̂e = 1 ≥ .
3

