Stochastic Packing Integer Programs with Few Queries∗
Takanori Maehara†1 and Yutaro Yamaguchi‡2,1

arXiv:1707.04020v2 [cs.DS] 1 Nov 2017

1

RIKEN Center for Advanced Intelligence Project
2
Osaka University

Abstract
We consider a stochastic variant of the packing-type integer linear programming
problem, which contains random variables in the objective vector. We are allowed to
reveal each entry of the objective vector by conducting a query, and the task is to
find a good solution by conducting a small number of queries. We propose a general
framework of adaptive and non-adaptive algorithms for this problem, and provide
a unified methodology for analyzing the performance of those algorithms. We also
demonstrate our framework by applying it to a variety of stochastic combinatorial
optimization problems such as matching, matroid, and stable set problems.

∗

This is the final draft of an accepted paper of SODA 2018.
Email: takanori.maehara@riken.jp
‡
Email: yutaro yamaguchi@ist.osaka-u.ac.jp
†

Contents
1 Introduction
1.1 Problem Formulation .
1.2 Our Contributions and
1.3 Related Work . . . . .
1.4 Organization . . . . .

.
.
.
.

1
1
1
3
4

2 General Framework
2.1 Two Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Proofs of Main Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
6
8

3 Constructing Witness Covers
3.1 Totally Dual Integral Case . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Non-TDI Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Exponentially Many Constraints . . . . . . . . . . . . . . . . . . . . . . . .

10
11
11
13

4 Applications
4.1 Matching Problems . . . . . . . . . . . . . . . . . . . . .
4.1.1 Bipartite Matching . . . . . . . . . . . . . . . . .
4.1.2 Non-bipartite Matching . . . . . . . . . . . . . .
4.1.3 k-Hypergraph Matching . . . . . . . . . . . . . .
4.1.4 k-Column Sparse Packing Integer Programming .
4.2 Matroid Problems . . . . . . . . . . . . . . . . . . . . .
4.2.1 Maximum Independent Set . . . . . . . . . . . .
4.2.2 Matroid Intersection . . . . . . . . . . . . . . . .
4.2.3 k-Matroid Intersection . . . . . . . . . . . . . . .
4.2.4 Matroid Matching . . . . . . . . . . . . . . . . .
4.2.5 Degree Bounded Matroid . . . . . . . . . . . . .
4.3 Stable Set Problems . . . . . . . . . . . . . . . . . . . .
4.3.1 Stable Set in Some Perfect Graphs . . . . . . . .
4.3.2 Stable Set in t-Perfect Graphs . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

13
13
14
14
16
18
19
19
20
21
22
23
24
25
26

5 Vertex Sparsification Lemma
5.1 Vertex Sparsification Lemma . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Usage of Vertex Sparsification Lemma . . . . . . . . . . . . . . . . . . . . .

27
27
29

. . . . . .
Technique
. . . . . .
. . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

1

Introduction

1.1

Problem Formulation

We study a stochastic variant of linear programming (LP) with the 0/1-integer constraint,
which enables us to discuss such variants of various packing-type combinatorial optimization problems such as matching, matroid, and stable set problems in a unified manner.
Specifically, we introduce the stochastic packing integer programming problem defined as
follows:
maximize c̃⊤ x
subject to Ax ≤ b,
x ∈ {0, 1}m ,

(1.1)

n×m
and b ∈ Zn+ , and Z+ denotes the set of nonnegative integers. The objective
where A ∈ Z+
vector c̃ ∈ Zm
+ is stochastic in the following sense.

• The entries c̃j (j = 1, 2, . . . , m) are independent random variables with some hidden
distributions for which we are given the following information: for each j,
−
+
− +
– the domain of c̃j is an integer interval {c−
j , cj + 1, . . . , cj } given by cj , cj ∈ Z+ ,
and
– the probability that c̃j = c+
j is at least a given constant p ∈ (0, 1] (which is
+
independent from j), i.e., c−
j ≤ c̃j ≤ cj − 1 occurs with probability at most
1 − p.

• When an instance (A, b, and the above information on c̃) is given, the realized values of
all c̃j , denoted by cj , are hiddenly fixed by nature according to the above distributions.
• For each j, we are allowed to conduct a query to reveal the realized value cj of c̃j .
Note that, since all c̃j are independent, we can consider at any time that each realized
value cj is determined just when a query for j is conducted.
Our aim is to find a feasible solution to (1.1) with a large objective value by conducting
a small number of queries. Note that we can definitely obtain an optimal solution by
solving the corresponding non-stochastic problem after conducting queries for all j. Our
interest is therefore in the trade-off between the number of queries and the quality of the
obtained solution.

1.2

Our Contributions and Technique

Contributions
We propose a general framework of adaptive and non-adaptive algorithms for the stochastic
packing integer programming problem. Here, an algorithm is non-adaptive if it reveals all
queried items simultaneously, and adaptive otherwise.
1

Table 1.1: Results obtained for the adaptive strategy, where n and m denote the number
of vertices in the graph and the ground set size of the matroids, respectively, in question.
We omit O(·) in the iteration column. Also, all the coefficients are assumed to be O(1).
For the non-adaptive algorithm, the approximation ratio is halved.
Problem
Approximation Ratio
Number of Iterations T
Bipartite Matching
1−ǫ
log(1/ǫp)/ǫp
1−ǫ
log(n/ǫ)/ǫp
Non-bipartite Matching
k-Hypergraph Matching
(1 − ǫ)/(k − 1 + 1/k)
(k log(k/ǫp) + 1/ǫ)/ǫp
(1 − ǫ)/2k
(k log(k/ǫp) + 1/ǫ)/ǫp
k-Column Sparse PIP
Matroid (Max. Independent Set)
Matroid Intersection
k-Matroid Intersection
Matroid Matching
Degree Bounded Matroid
Stable Set in Chordal Graphs
Stable Set in t-Perfect Graphs

1−ǫ
1−ǫ
(1 − ǫ)/k
(1
 − ǫ)2/3


each constraint
1 − ǫ  is violated 
at most d − 1

1−ǫ
1−ǫ

log(m/ǫ)/ǫp
log(m/ǫ)/ǫp
k log m log(m/ǫ)/ǫ3 p
log(n/ǫ)/ǫp
d log(n/ǫ)/ǫ2 p
log n/ǫp
log n log(n/ǫ)/ǫ3 p

In the adaptive strategy1 (which is formally shown in Algorithm 1 in Section 2.1), we
iteratively compute an optimal fractional solution x ∈ [0, 1]m to the optimistic LP (the
LP relaxation of (1.1) in which all the unrevealed c̃j are supposed to be c+
j ), and conduct
a query for each element j with probability xj . After the iterations, we find an integral
feasible solution to the pessimistic LP (in which all the unrevealed c̃j are supposed to be
c−
j ) by using some algorithms for the corresponding non-stochastic problem.
Similarly, in the non-adaptive strategy (Algorithm 2), we iteratively computes an optimal fractional solution x to the optimistic LP, and rounds down each element j (i.e.,
supposes c̃j to be c−
j instead of revealing cj ) with probability xj . After the iterations, we
reveal all the rounded-down elements and find an integral feasible solution to the pessimistic
LP.
In application, we need to decide how to execute the last step, and the performance of
the resulting algorithm depends on combinatorial structure of each specific problem. Our
main contribution is a proof technique for analyzing the performance of the algorithms.
Using this technique, we obtain results for the problem classes summarized in Table 1.1.
1

Algorithms 1 and 2 have freedom of the choices of algorithms for solving LPs and for finding an integral
solution in the last step; in particular, the latter depends heavily on each specific problem before formulated
as an integer LP. For this reason, we use the term “strategy” rather than “algorithm” to refer them.

2

Technique
Our technique is based on LP duality and enumeration. A brief overview of the technique
follows, where we focus on the adaptive strategy.
Let µ̃ be the optimal value of the omniscient LP (the LP relaxation of (1.1) in which
all c̃j are revealed). Note that µ̃ is a random variable depending on the realization of
c̃j . Our goal is to evaluate the number of iterations T such that the optimal value of the
pessimistic LP after T iterations is at least (1−ǫ)µ̃ with high probability2 . Then, if we have
an LP-relative α-approximation algorithm [31] (which outputs an integral feasible solution
whose objective value is at least α times the LP-optimal value) for the corresponding nonstochastic problem, we obtain a (1 − ǫ)α-approximate solution to our problem with high
probability.
To discuss the optimal value of the pessimistic LP, we consider the dual LP. By the LP
strong duality, it is sufficient to prove that the dual pessimistic LP after T iterations has
no feasible solution whose objective value less than (1 − ǫ)µ̃ with high probability.
Here, we introduce a finite set W ⊆ Rn+ of dual vectors, called a witness cover, for
every possible objective value µ (a candidate of µ̃) that satisfies the following property:
if all y ∈ W are infeasible, there is no feasible solution whose objective value is less than
(1 − ǫ)µ. Intuitively, W represents all the candidates for dual feasible solutions whose
objective values are less than (1 − ǫ)µ. We evaluate the probability that each y ∈ W
becomes infeasible after T iterations, and then estimate the sufficient number of iterations
by using the union bound for W .
In application, we only need to show the existence of a small witness cover for each
specific problem. We also give general techniques to construct small witness covers when
the considered problem enjoys some fruitful properties, e.g., when the constraint system
Ax ≤ b, x ≥ 0 is totally dual integral.

1.3

Related Work

Our stochastic packing integer programming problem generalizes the stochastic (unweighted)
matching problem [3, 4, 7] and the stochastic (unweighted) k-hypergraph matching problem [7], which have recently been studied in EC (Economics and Computation) community.
These problems are motivated to find an optimal strategy for kidney exchange [16, 33].
For the stochastic unweighted matching problem, Blum et al. [7] proposed adaptive and
non-adaptive algorithms that achieve approximation ratios of (1−ǫ) and of (1/2−ǫ), respectively, in expectation, by conducting O(log(1/ǫ)/p2/ǫ ) queries per vertex. Their technique is
based on the existence of disjoint short augmenting paths. Assadi et al. [3] proposed adaptive and non-adaptive algorithms that respectively achieve the same approximation ratios
2
Here we consider two types of randomness together. One is on the realization of c̃j , which is contained
in the “stochastic” input and determines the omniscient optimal value µ̃. The other is on the choice of
queried elements, which is involved in our “randomized” algorithms and affects the pessimistic LP obtained
after the iterations.

3

with high probability, by conducting O(log(1/ǫp)/ǫp) queries per vertex. Their technique
is based on the Tutte–Berge formula and vertex sparsification. Our proposed strategies
coincide with those of Assadi et al. when they are applied to the stochastic unweighted
matching problem and we always find integral optimal solutions to the LP relaxations, i.e.,
solve the (non-stochastic) unweighted matching problem every time. Our analysis looks
similar to theirs since they both use the duality, but ours is simpler and can also be used
for the weighted and capacitated situation. On the other hand, our analysis shows that
O(log(n/ǫ)/ǫp) queries per vertex are required3 , which is worse than theirs.
Recently, Assadi et al. [4] proposed a non-adaptive algorithm that achieves an approximation ratio of strictly better than 1/2 in expectation. However, this technique is tailored
to the unweighted matching problem, so we could not generalize it to our problem.
For the stochastic unweighted k-hypergraph matching problem, Blum et al. [7] proposed
adaptive and non-adaptive algorithms that find (2−ǫ)/k- and (4−ǫ)/(k2 +2k)-approximate
matchings, respectively, in expectation, by conducting O(sk,ǫ log(1/ǫ)/psk,ǫ ) queries per
vertex, where sk,ǫ is a constant depending on k and ǫ. Their technique is based on the
local search method of Hurkens and Schrijver [23]. For the adaptive case, our strategy
just achieves a worse approximation ratio than theirs because the same is true of the LPbased algorithm versus the local search. On the other hand, our algorithm requires an
exponentially smaller number of queries and runs in polynomial time both in n and 1/ǫ. In
addition, our algorithm can be used for the weighted case. For the non-adaptive case, our
algorithm outperforms theirs, all in terms of approximation ratio, the number of queries,
and running time.
Other variants of the stochastic packing integer programming problem with queries
have been studied. However, many of them employ the query-commit model [12,14,15,28],
in which the queried elements must be a part of the output. Some studies [1, 5, 10] also
impose additional budget constraints on the number of queries. In the stochastic probing
problem [2, 21, 22], both the queried and realized elements must satisfy given constraints.
Blum et al. [8] studied a stochastic matching problem without query-commit condition,
but with a budget constraint on the number of queries.

1.4

Organization

The rest of the paper is organized as follows. In Section 2, we describe our framework
of adaptive and non-adaptive algorithms for the stochastic packing integer programming
problem, and explain a general technique for providing a bound on the number of iterations.
In Section 3, we outline how to construct a small witness cover in general. In Section 4,
we apply the technique to a variety of specific combinatorial problems. In Section 5, we
provide a vertex sparsification lemma that can be used to improve the performance of the
3

Very recently, Behnezhad and Reyhani [6] claimed that the same algorithm as ours achieves an approximation ratio of 1 − ǫ by conducting a constant number of queries that depends on only ǫ and p. Their
analysis uses augmenting paths, like Blum et al. [7].

4

algorithms for several problems.

2

General Framework

Throughout the paper (with one exception as remarked later), we assume several reasonable
conditions of the constraints in (1.1).
n×m
and b ∈ Zn+ in (1.1) satisfy the following
Assumption 2.1. We assume that A ∈ Z+
4
three conditions :

1. b ≥ 1;
2. Aχj ≤ b for each j = 1, 2, . . . , m, where χj ∈ {0, 1}m denotes the j-th unit vector;
3. Ax ≤ b and x ≥ 0 imply x ≤ 1.
We give a general framework of adaptive and non-adaptive algorithms for our problem in
Section 2.1, and then describe a unified methodology for its performance analysis in Section
2.2. The main results are stated as Theorems 2.1 and 2.2, whose proofs are separately shown
in Section 2.3.

2.1

Two Strategies

To describe two strategies, we formally define two auxiliary problems, the optimistic LP
and the pessimistic LP. We define the optimistic vector c ∈ Zm
+ and the pessimistic vector
c ∈ Zm
as
follows:
+
(
cj j has been queried,
(2.1)
cj =
c+
otherwise,
j
(
cj j has been queried,
cj =
(2.2)
otherwise,
c−
j
where recall that cj ∈ Z+ denotes the realized value of c̃j . The optimistic and pessimistic
LPs are obtained from the original stochastic problem (1.1) by replacing the objective
vector c̃ with c and with c, respectively, and by relaxing the constraint x ∈ {0, 1}m to
x ∈ Rm
+ , where R+ denotes the set of nonnegative reals. By Assumption 2.1-3 (Ax ≤ b and
x ≥ 0 imply x ≤ 1), the relaxed constraint is equivalent to x ∈ [0, 1]m . Note that these
problems are no longer stochastic, i.e., contain no random variables.
4

The first two are assumed without loss of generality (by removing the corresponding constraints and
variables if violated). The third one is for simplicity, which holds for most of applications. The generalizability to remove it is discussed in Section 4.1.4 with a specific application.

5

Algorithm 1 Adaptive strategy.
1: for t = 1, 2, . . . , T do
2:
Find an optimal solution x to the optimistic LP.
3:
For each j = 1, . . . , m, conduct a query to reveal c̃j with probability xj .
4: end for
5: Find an integral feasible solution to the pessimistic LP and return it.
Algorithm 2 Non-adaptive strategy.
1: for t = 1, 2, . . . , T do
2:
Find an optimal solution x to the optimistic LP.
3:
For each j = 1, . . . , m, suppose c̃j = c−
j with probability xj .
4: end for
−
5: For every j with c̃j = cj supposed at Line 3, conduct a query to reveal c̃j .
6: Find an integral feasible solution to the pessimistic LP and return it.
First, we describe the adaptive strategy shown in Algorithm 1. In this strategy, we
iteratively compute an optimal solution x ∈ [0, 1]m to the optimistic LP, and reveal each
c̃j with probability xj . After T iterations, we find an integral feasible solution to the
pessimistic LP, where we have freedom of the choice of algorithms for the corresponding
non-stochastic problem. As remarked in Introduction, how to execute the last step depends
heavily on each specific problem.
Next, we describe the non-adaptive strategy shown in Algorithm 2. As with the adaptive
strategy, we solve the optimistic LP at each step. To be non-adaptive, the algorithm
tentatively assigns values to c̃j pessimistically instead of revealing their realized values.
After the iterations, it reveals all these values and then computes an integral feasible
solution to the pessimistic LP by some algorithms for the non-stochastic problem.

2.2

Performance Analysis

We now analyze the performance of algorithms within our framework. First, we consider
the adaptive strategy (Algorithm 1). As described in Section 1.1, we evaluate the trade-off
between the following two factors, each of which is reasonably decomposed into two factors.
(1) The number of conducted queries.
(1-a) Expected number of queries at Line 3. If this number is large, the algorithm may
reveal all relevant c̃j in a few iterations, making the algorithm trivial.
(1-b) Required number of iterations T at Line 1. If T is very large, then, as in (1-a),
the algorithm may reveal all relevant c̃j , making the algorithm trivial.
(2) The quality of the output solution. Basically, we want to find a feasible solution
6

to (1.1) with a large objective value, which is at most the omniscient optimal value
of (1.1) after all c̃j are revealed.
(2-a) Closeness between the pessimistic and omniscient LPs. The omniscient optimal
value of (1.1) is at most the optimal value µ̃ of the omniscient LP, which is
obtained by revealing all c̃j and by relaxing x ∈ {0, 1}m to x ∈ Rm
+ . If the
pessimistic LP-optimal value at Line 5 is close to µ̃, then, at least as an LP, the
pessimistic problem is close to the problem that we want to solve.
(2-b) LP-relative approximation ratio at Line 5. If one can find an integral feasible
solution such that the ratio between its objective value and the LP-optimal value
is bounded, then, combined with (2-a), a reasonable bound on the objective value
of the output solution can be obtained.
Essentially, (1-a) and (2-b) are properties of each specific problem and its LP formulation. Thus, we postpone these two factors to the discussion on applications in Section 4,
and focus on (1-b) and (2-a) in the general study in this section. That is, our goal here
is to estimate T such that the optimal value of the pessimistic LP after T iterations is at
least (1 − ǫ)µ̃ with high probability, where µ̃ is the optimal value of the omniscient LP and
ǫ > 0 is a parameter one can choose. Note again that µ̃ is a random variable depending on
the realization of c̃j .
To evaluate the number of iterations T , we consider the dual of the pessimistic LP:
minimize y ⊤ b
subject to y ⊤ A ≥ c⊤ ,
y ∈ Rn+ .

(2.3)

By the LP strong duality, it is sufficient to evaluate the probability that this dual LP has
no feasible solution whose objective value less than (1 − ǫ)µ̃.
Now we introduce the notion of a witness cover, which is the most important concept
in this study. Intuitively, a witness cover for µ ∈ R+ is a set of “representatives” of all the
dual feasible solutions with objective values of at most (1 − ǫ)µ.
n×m
, b ∈ Zn+ , and ǫ, ǫ′ ∈ R+ with 0 < ǫ′ ≤ ǫ. A finite set
Definition 2.1. Let A ∈ Z+
W ⊆ Rn+ of dual vectors is an (ǫ, ǫ′ )-witness cover for µ ∈ R+ if it satisfies the following
two properties.
⊤
⊤
⊤
⊤
1. For every c ∈ Zm
+ , if y A < c holds for all y ∈ W , then y A < c holds for all
n
⊤
y ∈ R+ with y b ≤ (1 − ǫ)µ.

2. y ⊤ b ≤ (1 − ǫ′ )µ holds for all y ∈ W .
During the iterations, the constraints in the dual pessimistic LP (2.3) become successively stronger. Hence, for any witness cover W for the omniscent LP-optimal value µ̃,
7

every y ∈ W eventually becomes infeasible to (2.3) (by Condition 2). By evaluating the
probability that all y ∈ W become infeasible after T iterations, we obtain a bound on
the required number of iterations. Note again that µ̃ is a random variable, and hence we
assume that there exists a relatively small witness cover for every possible objective value
µ, which can be restricted to µ ≥ 1 due to Assumption 2.1-2 (see the proof for the detail).
Theorem 2.1. Let M ∈ R+ , and suppose that there exists an (ǫ, ǫ′ )-witness cover of size
at most M µ for every µ ≥ 1. Then, by taking
 
∆c
M
T ≥ ′ log
,
(2.4)
ǫp
δ
the pessimistic LP at Line 5 of Algorithm 1 has a (1 − ǫ)-approximate solution with prob−
ability at least 1 − δ, where ∆c = maxj (c+
j − cj ) and 0 < δ < 1.
For the non-adaptive algorithm (Algorithm 2), by conducting a similar analysis with a
case analysis, we obtain the required number of iterations with a provable approximation
ratio.
Theorem 2.2. Under the same assumption as Theorem 2.1, by taking T as (2.4), the pessimistic LP at Line 6 of Algorithm 2 has a (1 − ǫ)/2-approximate solution with probability
at least 1 − δ.
These theorems show that if there exists a small witness cover (for each possible µ),
Algorithms 1 and 2 will find good solutions in a reasonable number of iterations. It is worth
emphasizing that we only have to prove the existence of such a witness cover, i.e., we do
not have to construct it algorithmically. We discuss how to prove the existence of such
witness covers (i.e., how to construct them theoretically) in general and in each specific
application, in Sections 3 and 4, respectively.

2.3

Proofs of Main Theorems

Proof of Theorem 2.1
Let µ̃ be the optimal value of the omniscient LP. If µ̃ = 0 then the statement obviously
holds (with probability 1). Thus we restrict ourselves to the case when µ̃ > 0. Note that
µ̃ > 0 implies µ̃ ≥ 1 as follows. If µ̃ > 0 then c̃j = cj ≥ 1 for some j, and by Assumption
⊤
2.1-2, the j-th unit vector χj ∈ Rm
+ is feasible (i.e., Aχj ≤ b); therefore µ̃ ≥ c χj = cj ≥ 1.
For each µ ≥ 1, fix an (ǫ, ǫ′ )-witness cover Wµ of size |Wµ | ≤ M µ . We first evaluate the
probability that each y ∈ Wµ̃ is feasible after T iterations. Since some c̃j is newly revealed,
some constraints may be violated (i.e., (y ⊤ A)j < cj may happen). Once y has become
infeasible, it never returns to feasible due to the monotonicity of c throughout Algorithm
1. Therefore, y is feasible after T iterations only if y is feasible at every iteration step.

8

Fix t = 1, 2, . . . , T , and we evaluate the probability that a vector y in each witness
cover that is feasible at the beginning of the t-th step remains feasible at the end of the
step. Let c, c ∈ Zm
+ be the optimistic and pessimistic vectors, respectively, at Line 2 in the
t-th step, and µ, µ ∈ Rm
+ the optimal values of the corresponding LPs. Note that µ and µ
are respectively upper and lower bounds on µ̃ at that time.
Claim 2.1. For every µ ∈ [µ, µ] and each y ∈ Wµ with y ⊤ A ≥ c⊤ , the probability that y
is feasible after Line 3 is at most exp (−ǫ′ pµ/∆c ).
Proof. Since y is feasible at the beginning of the step, y is feasible after Line 3 only if no
possibly violated constraint is revealed to be c+
j . We can evaluate the number of possibly
violated constraints at this step using the following inequality:
c⊤ x ≤ c⊤ x + y ⊤ (b − Ax) = y ⊤ b + (c⊤ − y ⊤ A)x,

(2.5)

where x ∈ [0, 1]m is the optimal solution to the optimistic LP obtained in Line 2. Since the
optimistic vector c dominates the actual vector c̃ (irrespective of which values are realized),
we have c⊤ x ≥ µ̃. Since y ∈ Wµ , we have y ⊤ b ≤ (1 − ǫ′ )µ. Therefore, by (2.5), we see
X
X
(c+
xj ,
(2.6)
ǫ′ µ ≤ (c⊤ − y ⊤ A)x ≤
j − cj )xj ≤ ∆c
j : violated

j : violated

where we say that j is violated if (y ⊤ A)j < cj for the realized value cj of c̃j , and note that
+
⊤
cj ≤ c+
j , (y A)j ≥ cj , and cj ≥ cj − ∆c for every j. Since the left-hand side of (2.6) is
positive, there must exist possibly violated constraints in the support of x, and if one of
them, say c̃j , is revealed (with probability xj ) as c+
j (with probability at least p), then y
becomes infeasible. Then the probability that y is still feasible after this step is at most




Y
X
−pǫ′ µ


.
(2.7)
(1 − pxj ) ≤ exp −p
xj ≤ exp
∆c
j : violated

j : violated

By applying Claim 2.1 to µ̃ (the omniscient LP-optimal value) T times, we obtain that
the probability that each y ∈ Wµ̃ is feasible after T iterations is at most exp (−ǫ′ pµ̃T /∆c ).
By the union bound, the probability that Wµ̃ has at least one feasible solution to the dual
pessimistic LP (2.3) after T iterations is at most |Wµ̃ | exp (−ǫ′ pµ̃T /∆c ), which is at most
exp (µ̃ log M − ǫ′ pµ̃T /∆c ). By taking T ≥ ∆c log(M/δ)/ǫ′ p, the latter value is bounded
by exp(µ̃ log δ) ≤ δ (recall that µ̃ ≥ 1 and 0 < δ < 1). By the definition of witness cover
and strong duality, we conclude that the optimal value of the pessimistic LP at Line 5 of
Algorithm 1 is at least (1 − ǫ)µ̃ with probability at least 1 − δ.
Proof of Theorem 2.2
The following proof is a simple extension of Theorem 5.1 in Assadi et al. [3] for the stochastic
matching problem.
9

Let µ̃ be the optimal value of the omniscient LP, and we assume µ̃ ≥ 1 as in the proof
of Theorem 2.1. In the above analysis of Algorithm 1, it is ensured that there exists a
solution x with c⊤ x ≥ µ̃, which ensured that the last pessimistic LP in Algorithm 1 has an
optimal value of at least (1 − ǫ)µ̃. However, in the non-adaptive case, we may not be able
to find such a solution because each c̃j is not revealed but is rounded-down.
To overcome this issue, we define µ̃′ ∈ R+ as the minimum objective value obtained at
Line 2 of Algorithm 2. Note that, since the optimal value of the optimistic LP solved at
Line 2 is monotonically non-increasing, µ̃′ is the objective value obtained at the T -th step.
By applying Claim 2.1 to µ̃′ (instead of µ̃) T times, we obtain the following claim.
Claim 2.2. By taking T ≥ ∆c log(M/δ)/ǫ′ p in Algorithm 2, the optimal value of the
pessimistic LP at Line 6 is at least (1 − ǫ)µ̃′ with probability at least 1 − δ.
µ̃′

If µ̃′ ≥ µ̃/2, we can immediately prove the theorem. Thus, we consider the case
< µ̃/2, obtaining the following claim.

Claim 2.3. If µ̃′ < µ̃/2, the optimal value of the pessimistic LP at Line 6 of Algorithm 2
is at least µ̃/2.
Proof. We use the subscripts R and N to denote the revealed and unrevealed entries in the
primal vector, respectively, i.e., c̃R = cR has been realized and the rest c̃N has not been
revealed. Let x∗ ∈ Rm
+ be an optimal solution to the (primal) omniscient LP (which is a
random variable depending on the realization of c̃N ). We then have
∗
⊤ ∗
c⊤
R xR + c̃N xN = µ̃,

(2.8)

Since (0, x∗N ) ∈ Rm
+ is a feasible solution to the optimistic LP at the last iteration, we have
∗
′
c+⊤
N xN ≤ µ̃ < µ̃/2.

(2.9)

Therefore, the objective value for x∗ in the pessimistic LP at Line 6 is bounded by
∗
⊤ ∗
⊤
+⊤ ∗
c⊤ x∗ ≥ c⊤
R xR ≥ cR xR + (c̃N − cN )xN > µ̃/2.

(2.10)

This means that the pessimistic LP-optimal value is at least µ̃/2.
This concludes the theorem.

3

Constructing Witness Covers

Our technique requires us to prove the existence of a small witness cover. Here, we describe
general strategies for constructing small witness covers.

10

3.1

Totally Dual Integral Case

A system Ax ≤ b, x ≥ 0 is totally dual integral (TDI) if, for every integral objective vector
c ∈ Zm , the dual problem min{ y ⊤ b : y ⊤ A ≥ c⊤ , y ≥ 0 } has an integral optimal solution
y ∈ Zn+ (unless it is infeasible). Note that a TDI system admits an integral optimal solution,
i.e., it is integral. See, e.g., [34] for more detail.
If the system is TDI, we can construct a witness cover by enumerating all possible
integral vectors as follows.
n
Lemma 3.1. If the system Ax ≤ b, x ≥ 0 is TDI,
  the following
 set W ⊆ R+ is an
(ǫ, ǫ)-witness cover for µ ≥ 1 such that |W | = exp O µ log(1 + nµ ) :

W = { y ∈ Zn+ : y ⊤ b ≤ (1 − ǫ)µ }.

(3.1)

Proof. It is clear that W is an (ǫ, ǫ)-witness cover for µ, so it only remains to evaluate the
cardinality of W . We see that |W | is at most the number of nonnegative vectors whose
entries sum to at most ⌊µ⌋, which can be counted by distributing k (≤ ⌊µ⌋) tokens among
n entries, giving
|W | ≤


⌊µ⌋ 
X
n+k−1
k=0

k

=




 



n + ⌊µ⌋
e(n + ⌊µ⌋) ⌊µ⌋
O µ log 1+ n
µ
=e
.
≤
⌊µ⌋
⌊µ⌋

(3.2)

Note that the same counting technique can be used when the system is totally dual
1/k-integral (TDI/k), i.e., the existence of a dual optimal solution where each entry is a
multiple of 1/k is guaranteed.

3.2

Non-TDI Case

If the system is not TDI, we have to deal with fractional dual vectors. To enumerate these
fractional vectors, we discretize the dual vectors, requiring the discretization to have the
following property: if there exists a feasible y such that y ⊤ b ≤ (1−ǫ)µ, there exists a feasible
discretized y ′ such that y ′⊤ b ≤ (1 − ǫ/2)µ. Here, we consider two possible situations: Dual
Sparse Case and General Case.
Dual Sparse Case
If there exists a sparse dual optimal solution, we can simply discretize the dual vectors to
obtain a good discretized solution as follows.
Lemma 3.2. For positive µ, ǫ, and γ, if there
exists y ∈ Rn+ such that y ⊤ b ≤ (1 − ǫ)µ
Q
n
and |supp(y)| ≤ γµ, then there exists y ′ ∈ i=1 (ǫ/2bi γ)Z+ such that y ′⊤ A ≥ y ⊤ A and
y ′⊤ b ≤ (1 − ǫ/2)µ.
11

Proof. A suitable y ′ can be obtained by rounding up the i-th entry of y to the next multiple
of ǫ/2bi γ for each i.
Now that the existence of a discretized solution whose objective value is almost the
same as any sparse solution has been guaranteed, we can construct a witness cover by
enumerating all the discretized vectors.
n
Lemma 3.3. Under the assumption given in Lemma
 3.2,
 the
 following set
W ⊆ R+ is an
n
(ǫ, ǫ/2)-witness cover for µ ≥ 1 such that |W | = exp O µ γ log γµ
+ 1ǫ
:

W =

(


n 

Y
ǫ
ǫ
y∈
µ, |supp(y)| ≤ γµ
Z+ : y ⊤ b ≤ 1 −
2bi γ
2
i=1

)

.

(3.3)

Proof. By Lemma 3.2, W is an (ǫ, ǫ/2)-witness cover for µ. We evaluate the cardinality of
W as follows. We first select s (≤ γµ) entries for the support of y, and then distribute
k (< 2µ/ǫ) tokens among these entries, where each token contributes ǫ/2 to the objective
value. In the nontrivial case when µ1 := γµ ≥ 1 and µ2 := 2µ/ǫ ≥ 1, the number of these
patterns is bounded by
⌊µ1 ⌋ 


2⌋ 
X n ⌊µ
X
s+k−1
s
k
s=1
k=0




e(⌊µ1 ⌋ + ⌊µ2 ⌋) ⌊µ2 ⌋
en ⌊µ1 ⌋
⌊µ2 ⌋
≤ ⌊µ1 ⌋
⌊µ1 ⌋
⌊µ2 ⌋


 
⌊µ1 ⌋
en
n
⌊µ1 ⌋+⌊µ2 ⌋
≤ ⌊µ1 ⌋
.
⌊µ2 ⌋ e
= exp O µ1 log
+ µ2
⌊µ1 ⌋
µ1

|W | ≤

General Case
When the optimal dual solutions are not sparse, the results of simple discretization are
useless. However, even in such a case, there is a good discretized solution. Let y be
a feasible dual vector. Then by applying randomized rounding [32] to y, we obtain a
suitable discretized vector y ′ with a positive probability. Formally, the following theoretical
guarantee is obtained.
Theorem 3.1 (Kolliopoulos and Young [25]). Any feasible LP miny { y ⊤ b : y⊤ A ≥c⊤ , y ≥

0 } has a (1+ǫ/2)-approximate solution whose entries are multiples of θ = Θ
m is the dimension of c.

ǫ2
log m

, where

We use this theorem as an existence theorem. If there is an optimal dual solution with
objective value of at most (1 − ǫ)µ, this theorem shows that there exists a dual feasible
solution whose entries are multiples of θ with an objective value of at most (1+ǫ/2)(1−ǫ)µ ≤
12

(1− ǫ/2)µ. By enumerating the dual vectors whose entries are multiples of θ, we can obtain
a witness cover.
 2 
Lemma 3.4. Let θ = Θ logǫ m . The following set W ⊆ Rn+ is an (ǫ, ǫ/2)-witness cover
 


m
n
for µ ≥ 1 such that |W | = exp O µ log
log
1
+
:
µ
ǫ2
W =

n


ǫ o
µ .
y ∈ θZn+ : y ⊤ b ≤ 1 −
2

(3.4)

Proof. By Theorem 3.1, W is an (ǫ, ǫ/2)-witness cover for µ. We evaluate the cardinality
of W as follows. Let µ′ := ⌊µ/θ⌋. The number of ways of distributing k (≤ µ′ ) tokens
among n entries is bounded by

µ′ 
X
n+k−1

 ′
e(n + µ′ ) µ
≤µ
|W | ≤
k
µ′
k=0


 
θn
µ
′ µ′ (1+log(1+n/µ′ ))
log 1 +
.
≤µe
= exp O
θ
µ

3.3

′



(3.5)

Exponentially Many Constraints

Some problems, such as the non-bipartite matching problem and matroid problems, have
exponentially many constraints. In such cases, it is impossible to enumerate all the candidates naively as we have done in the previous sections.
Sometimes, this difficulty is overcome by identifying the granularity of the dual solution
(i.e., TDI, dual sparse, or general), and then bounding the number of possible dual patterns
by exploiting the combinatorial structure; see next section for concrete examples.

4

Applications

In this section, we demonstrate our proposed framework by applying it to several stochastic
combinatorial problems. We only describe the results for the adaptive strategy (Algorithm
1) as the results for the non-adaptive strategy (Algorithm 2) can easily be obtained analogously.

4.1

Matching Problems

In this section, unless otherwise noted, n denotes the number of vertices in the (hyper)graph
in question.

13

4.1.1

Bipartite Matching

We first demonstrate how to use our technique for the bipartite matching problem. Let
(V, E) be a bipartite graph and c̃ ∈ ZE
+ be a stochastic edge weight. The bipartite matching
problem can then be represented as
X
maximize
c̃e xe
e∈E
X
(4.1)
subject to
xe ≤ 1 (u ∈ V ),
e∈δ(u)

x ∈ {0, 1}E ,

where δ(u) = { e ∈ E : u ∈ e }. The Kőnig–Egerváry theorem [19, 26] shows that the LP
relaxation of this system is TDI, so Algorithm 1 has an approximation ratio of (1 − ǫ)
with high probability for sufficiently large T . Moreover, if the algorithm finds an integral
solution to the optimistic problem in Line 2, it reveals a matching in each iteration, and
hence at most T edges per vertex in total. Finally, by Lemma 3.1, there exists an (ǫ, ǫ)witness cover of size eO(µ log n) for each µ ≥ 1. We can therefore obtain the following result
from Theorem 2.1.
Corollary 4.1. For the bipartite matching problem, by taking T = Ω(∆c log(n/ǫ)/ǫp),
Algorithm 1 outputs a (1 − ǫ)-approximate solution with probability at least 1 − ǫ.
This result can be improved by using the vertex sparsification lemma in Section 5.
4.1.2

Non-bipartite Matching

Next, we consider the non-bipartite matching problem. Let (V, E) be a graph and c̃ ∈ ZE
+
be a stochastic edge weight. A naive formulation of this problem is as follows:
X
c̃e xe
maximize
e∈E
X
(4.2)
subject to
xe ≤ 1 (u ∈ V ),
e∈δ(u)

x ∈ {0, 1}E .

It is known that the LP relaxation of this system is TDI/2 (totally dual half-integral) and
has an integrality gap of 3/2 [34]. Therefore, by the same argument as in the bipartite
matching problem, we can show that Algorithm 1 has an approximation ratio of (2 − ǫ)/3
with high probability if T = Ω(∆c log(n/ǫ)/ǫp).
To improve this approximation ratio, we consider a strengthened formulation by adding

14

the blossom inequalities:
maximize
subject to

X

c̃e xe

e∈E
X

xe ≤ 1

(u ∈ V ),
(4.3)

e∈δ(u)

X

e∈E(S)



|S|
xe ≤
2

x ∈ {0, 1}E ,



(S ∈ Vodd ),

where E(S) = { e ∈ E : e ⊆ S } and Vodd = { S ⊆ V : |S| is odd and at least 3 }.
Cunningham and Marsh [13] showed that this system is TDI, so our algorithm has an
approximation ratio of (1 − ǫ) with high probability for sufficiently large T . Moreover, the
number of revealed edges is at most T per vertex.
The only remaining issue is the number of iterations. Since the system (4.3) has exponentially many constraints, we have to exploit its combinatorial structure to reduce the
number of possibilities. The dual problem is given by
X
X  |S| 
minimize
yu +
zS =: τ (y, z)
2
u∈V
S∈Vodd X
(4.4)
subject to yu + yv +
zS ≥ c̃e
(e = {u, v} ∈ E),
S∈Vodd : {u,v}⊆S

y ∈ RV+ , z ∈ RV+odd .

For µ ≥ 1, let us define a set W ⊆ RV+ × RV+odd by
o
n
W = (y, z) ∈ ZV+ × ZV+odd : τ (y, z) ≤ (1 − ǫ)µ .

(4.5)

It is clear that W is an (ǫ, ǫ)-witness cover, and we can evaluate the size of W as follows.

Claim 4.1. |W | = eO(µ log n) .
Proof. WePcount the candidates for y and z separately.
Since i yi < µ, the number of candidates for y is at most
⌊µ⌋  
X
n
k=0

k

≤ (⌊µ⌋ + 1)



en
⌊µ⌋

⌊µ⌋

= eO(µ log n) .

(4.6)

To count the number of candidates for z, we regard z as a multiset, e.g., if zS = 2 then
we think there are two S. Let si (i = 1, 2, . . . , k) be the size of each set contained in z.
Then we have
j s k
j s k
1
k
+ ··· +
< 3µ.
(4.7)
s1 + · · · + sk ≤ 3
2
2
15

Therefore, the number of candidates for z is given by
⌊µ⌋
X

X

k=0 s1 +···+sk ≤3µ
s1 ,...,sk ≥3

    X

n
n
3 ⌊µ⌋ + k − 1 µ
···
≤
n = eO(µ log n) .
s1
sk
k

(4.8)

k

By multiplying the number of candidates for y and z, we obtain the required result.
Therefore, we obtain the following.
Corollary 4.2. For the non-bipartite matching problem, by taking T = Ω(∆c log(n/ǫ)/ǫp),
Algorithm 1 outputs a (1 − ǫ)-approximate solution with probability at least 1 − ǫ.
The same analysis can be applied to the (simple) b-matching problem.
Relationship to the analysis of Assadi et al. The adaptive and non-adaptive algorithms of Assadi et al. [3] for the unweighted non-bipartite matching problem are within
our framework (Algorithms 1 and 2, respectively), and their analysis utilizes the Tutte–
Berge formula. They showed that the required number of iterations is O(log(n/ǫµ)/ǫp),
and it is reduced to O(poly(p, 1/ǫ)) by using the vertex sparsification lemma.
For the unweighted problem, our analysis gives a weaker result than theirs. However,
since no simple alternative to the Tutte–Berge formula for the weighted problem is known,
our analysis is more general than theirs.
4.1.3

k-Hypergraph Matching

Let (V, E) be a k-uniform hypergraph, i.e., E is a set family on V whose element e ∈ E
has size exactly k. Let c̃ ∈ ZE
+ be a stochastic edge weight. The k-hypergraph matching
problem can be represented as
X
maximize
c̃e xe
e∈E
X
(4.9)
subject to
xe ≤ 1 (u ∈ V ),
e∈δ(u)

x ∈ {0, 1}E ,

where δ(u) = { e ∈ E : u ∈ e }. Chan and Lau [9] proved that the LP relaxation of
the above system has an integrality gap of α := 1/(k − 1 + 1/k), and they also proposed
an LP-relative α-approximation algorithm.
P Since at most one edge per vertex is revealed
in expectation due to the constraint
e∈δ(u) xe ≤ 1, the expected number of revealed
hyperedges per vertex is O(T ) in total.

16

The only remaining issue is the number of iterations. Since the system (4.9) has polynomially many constraints and is not TDI, we have to discretize the dual variables. The
corresponding dual problem is given by
X
minimize
yu
u∈V
X
(4.10)
subject to
yu ≥ c̃e (e ∈ E),
u∈e

y ∈ RV+ .

Here, we show that the dual optimal solution is sparse.
Claim 4.2. If the optimal value is less than µ, then there exists a dual optimal solution
y ∈ RV+ such that |supp(y)| < kµ.
Proof. Let x ∈ RE
optimal
solution. We can assume that xe > 0 only if
+ be a primal
P
P
c̃e ≥ 1. Therefore, we have e xe ≤ e c̃e xe < µ. Since each hyperedge consists of exactly
k elements, we have
X X
X
xe = k
xe < kµ.
(4.11)
u∈V e∈δ(u)

e∈E

This shows that less than kµ inequalities can hold in equality. Therefore, by complementary
slackness, the corresponding dual optimal solution y satisfies |supp(y)| < kµ.
Therefore, by Lemma 3.3,there
(ǫ, ǫ/2)-witness cover for each µ ≥ 1 of size
 exists an 
n
1
at most M µ , where M = exp O k log kµ + ǫ . Thus we obtain the following.

Corollary 4.3. For the k-hypergraph matching problem, by taking T = Ω(∆c (k log(n/ǫ)+
1/ǫ)/ǫp), Algorithm 1 outputs a (1− ǫ)/(k − 1+ 1/k)-approximate solution with probability
at least 1 − ǫ.
This result is improved by using the vertex sparsification lemma in Section 5.

Comparison with Blum et al. Blum et al. [7] provided adaptive and non-adaptive
algorithms for the unweighted k-hypergraph matching problem based on local search of
Hurkens and Schrijver [23]. Their adaptive algorithm has approximation ratio of (2 − ǫ)/k
in expectation by conducting a constant number of queries per vertex.
For unweighted problem, our algorithm has a worse approximation ratio than theirs.
However, our algorithm has four advantages: it requires exponentially smaller number of
queries; it runs in polynomial time both in n and 1/ǫ; it is applied to the weighted problem
with the same approximation ratio; and it has a stronger stochastic guarantee, i.e., not in
expectation but with high probability.
17

Remark 4.1. For unweighted k-hypergraph matching problem, Chan and Liu [9] showed
that there is a packing LP with an integrality gap of 2/(k + 1). Note that the rounding
algorithm for this LP is not known. Using this formulation, we obtain a (2 − ǫ)/(k + 1)
approximation algorithm which conducts Oǫ,p (log2 n) queries and runs in non-polynomial
time (i.e., it performs exhaustive search).
4.1.4

k-Column Sparse Packing Integer Programming

The k-column sparse packing integer programming problem is a common generalization of
the k-hypergraph matching problem and the knapsack problem, and can be represented as
follows (the formulation itself just rewrites (1.1) by using the entries of the matrix and of
the vectors):
maximize

m
X

c̃j xj

j=1

subject to

m
X

aij xj ≤ bi (i = 1, . . . , n),

(4.12)

j=1

x ∈ {0, 1}m ,
where “k-column sparse” means that |{ i : aij 6= 0 }| ≤ k for each j ∈ {1, . . . , m}. Without
loss of generality, we assume that aij ≤ bi for all i ∈ {1, . . . , n} and j P
∈ {1, . . . , m}.
The main difference from the other problems is that the system j aij xj ≤ bi , x ≥ 0
does not imply xj ≤ 1. Instead, we have xj ≤ wj , where wj = mini : aij 6=0 bi /aij . Let
w = maxj wj . By modifying Algorithm 1 to reveal each xj with probability xj /w, we
obtain the same approximation guarantee with w times larger number of iterations.
Parekh [30] proposed an LP-relative (1/2k)-approximation algorithm for general k and
a (1/3)-approximation algorithm for k = 2, which encompasses the demand matching
problem [35]. The expected number of revealed elements for each constraint i is O(bi T ),
because we have
X
X
xj ≤
aij xj ≤ bi .
(4.13)
j : aij 6=0

j

The only remaining issue is the number of iterations. Using the same approach as for
the k-hypergraph matching problem, we obtain the following result.
Corollary 4.4. For the k-column sparse packing integer programing problem, by taking
T = Ω(∆c w(k log(n/ǫ) + 1/ǫ)/ǫp), Algorithm 1 outputs a (1 − ǫ)/2k-approximate solution
with probability at least 1 − ǫ.

18

4.2

Matroid Problems

Now we apply our technique to matroid-related optimization problems (see, e.g., [34] for
basics of matroids and related optimization problems). In this section, without otherwise
noted, m denotes the ground set size of the matroids in question.
4.2.1

Maximum Independent Set

Let M = (E, I) be a matroid on a finite set E, and let r : 2E → Z+ be its rank function.
A set S ⊆ E is a flat if r(S ∪ e) 6= r(S) for all e ∈ E \ S, and let FM denote the family
of flats in M. For a subset S ⊆ E, the smallest flat containing S is called the closure of
S. We assume that the rank of the matroid is relatively small to ensure that Algorithm 1
does not reveal all the elements.
Let c̃ ∈ ZE
+ be a stochastic weight. The maximum independent set problem can be
represented as follows:
X
maximize
c̃e xe
e∈E
X
(4.14)
subject to
xe ≤ r(S) (S ⊆ E),
e∈S

x ∈ {0, 1}E .

Edmonds [18] showed that the LP relaxation of the above system is TDI, so our algorithm
has an approximation ratio of (1 − ǫ) with high probability. Moreover, the number of
revealed elements is O(rT ), where r = r(E) is the rank of the matroid in question.
The only remaining issue is the number of iterations. Since the system has exponentially
many constraints, we have to exploit the combinatorial structure of the problem to reduce
the number of possibilities. The dual problem is given by
X
r(S)yS
minimize
subject to

S⊆E
X

yS ≥ c̃e (e ∈ E),

(4.15)

S⊆E : e∈S
E

y ∈ R2+ .

Since the closure of each S ⊆ E contributes the objective value by r(S) and contains all
elements in S, we can restrict the supports of y to the subfamilies of FM . Then, for µ ≥ 1,
E
let us define a set W ⊆ R2+ by




X
E
W = y ∈ Z2+ :
r(S)yS ≤ (1 − ǫ)µ, supp(y) ⊆ FM .
(4.16)


S∈FM

It is clear that W is an (ǫ, ǫ)-witness cover, and we can evaluate the size of W as follows.
19

Claim 4.3. |W | = eO(µ log m) .
Proof. To evaluate the size of W , as for the non-bipartite matching problem, we regard y
as a multiset. Let r1 , . . . , rk be the sizes of each set in y. Then we have r1 + · · · + rk < µ.
Since each flat is the closure of some independent set, the number of flats of rank r is
at most the number of independent sets of size r, which is at most m
r . Therefore, the
number of dual candidates for y is given by
⌊µ⌋
X

X

k=0 r1 +···+rk ≤µ
r1 ,...,rk ≥1

 
 
m
m
···
≤ eO(µ log m) .
r1
rk

(4.17)

Therefore, we obtain the following.
Corollary 4.5. For the maximum independent set problem, by taking T = Ω(∆c log(m/ǫ)/ǫp),
Algorithm 1 outputs a (1 − ǫ)-approximate solution with probability at least 1 − ǫ.
4.2.2

Matroid Intersection

The same technique can also be applied to the matroid intersection problem. Let Mj =
(E, Ij ) (j = 1, 2) be two matroids whose rank functions are rj : 2E → Z+ , and c̃ ∈ ZE
+ be
a stochastic weight. The weighted matroid intersection problem can be represented as
X
maximize
c̃e xe
e∈E
X
(4.18)
subject to
xe ≤ rj (S) (S ⊆ E, j ∈ {1, 2}),
e∈S

x ∈ {0, 1}E .

Edmonds [18] showed that the LP relaxation of the above system is TDI, so our algorithm
has an approximation ratio of (1−ǫ) with high probability for sufficiently large T . Moreover,
the number of revealed elements is O(r ∗ T ), where r ∗ is the maximum rank of a common
independent set in the two matroids.
The only remaining issue is the number of iterations. As the analysis of the maximum
E
E
independent set problem, we can restrict the supports of dual vectors y ∈ R2+ × R2+ to
the subfamilies of FM1 × FM2 , and we obtain the following by the same argument.
Corollary 4.6. For the matroid intersection problem, by taking T = Ω(∆c log(m/ǫ)/ǫp),
Algorithm 1 outputs a (1 − ǫ)-approximate solution with probability at least 1 − ǫ.5
5

Note that the bipartite matching problem is a special case of the matroid intersection problem, and
Corollary 4.1 is obtained from a naive application of this result. Using the vertex sparsification lemma
shown in Section 5, a stronger result is obtained for bipartite matching (Corollary 5.1).

20

4.2.3

k-Matroid Intersection

Let Mj = (E, Ij ) (j = 1, 2, . . . , k) be k matroids whose rank functions are rj : 2E → Z+ ,
and c̃ ∈ ZE
+ be a stochastic weight. The k-matroid intersection problem can be represented
as
X
maximize
c̃e xe
e∈E
X
(4.19)
subject to
xe ≤ rj (S) (S ⊆ E, j ∈ {1, 2, . . . , k}),
e∈S

x ∈ {0, 1}E .

The important difference between the 2-intersection and k-intersection (k ≥ 3) problems is
that the latter is NP-hard in the non-stochastic case. Moreover, the LP relaxation of the
system is not a kind of TDI.
Adamczyk et al. [2] proposed an LP-relative (1/k)-approximation algorithm. The expected number of revealed elements is O(r̂T ), where r̂ is the minimum of the ranks of the
k matroids.
The only remaining issue is the number of iterations. Since the LP relaxation of (4.19)
is not TDI, we have to discretize the dual variables. Moreover, since we could not prove
the dual optimal solution is sparse, we use Theorem 3.1.
 V k
 2 
by
For θ = Θ logǫ m and µ ≥ 1, let us define a set W ⊆ R2+
W =





V k
:
(y 1 , . . . , y k ) ∈ θZ2+
X

rj (S)ySj

j,S


ǫ
j
µ, supp(y ) ⊆ FMj (∀j = 1, . . . , k) .
≤ 1−
2


(4.20)

By Theorem 3.1, W is an (ǫ, ǫ/2)-witness cover, and we can evaluate its size as follows.
Claim 4.4. |W | = eO(µk log

2

m/ǫ2 ) .

Proof. To evaluate the size of W , as for the maximum independent set problem, we count
each y j separately. As same as the matroid case, we regard y j as a multiset in which
each set S contributes θ. Let r1 , . . . , rk be the size of each set in y j . Then we have
r1 + · · · + rk < µ/θ. By the same argument as for the matroid case, the number of dual
candidates for y j is at most eO((µ/θ) log m) . By multiplying the numbers of candidates for
the k coordinates, we obtain the required result (recall θ = Θ(ǫ2 / log m)).
Therefore, we obtain the following.
Corollary 4.7. For the k-matroid intersection problem, by taking T = Ω(∆c k log m log(m/ǫ)/ǫ3 p),
Algorithm 1 outputs a (1 − ǫ)/k-approximate solution with probability at least 1 − ǫ.
21

4.2.4

Matroid Matching

The matroid matching problem is a common generalization of the matching problem and
the matroid intersection problem. Let (V, E) be a graph with |V | = n, M = (V, I) be
a matroid whose rank function is r : 2V → Z+ , and c̃ ∈ ZE
+ be a stochastic edge weight.
The task is to find a maximum-weight subset of edges such that the endpoints form an
independent set of the matroid M. Vande Vate [37] proposed the following LP formulation:
X
maximize
c̃e xe
e∈E
X
(4.21)
subject to
a(S, e)xe ≤ r(S) (S ⊆ V ),
e∈E

x ∈ {0, 1}E ,

where a(S, e) = |S ∩ e|. Gijswijt and Pap [20] showed that the system is TDI/2, and
proposed a polynomial-time algorithm for obtaining a fractional optimal solution. A (2/3)approximate integral solution can be obtained by rounding this solution by the procedure
of Lee, Sviridenko,
and Vondrák
[27]6 . The expected number of revealed edges is O(T ) per
P
P
vertex since e∈δ(u) xe = e∈E a({u}, e)xe ≤ r({u}) ≤ 1.
The only remaining issue is the number of iterations. Since it has exponentially many
constraints, we have to exploit its combinatorial structure to reduce the number of possibilities. The dual problem is given by
X
r(S)yS
minimize
subject to

S⊆V
X

a(S, e)yS ≥ c̃e (e ∈ E),

(4.22)

S⊆V : e∈S
V
y ∈ R2+ .

Since a(S, e) is monotonically nondecreasing in S, we can restrict the support of y to the
set of flats. We define a witness cover by




X
1 V
r(S)yS ≤ (1 − ǫ)µ, supp(y) ⊆ FM .
(4.23)
W = y ∈ Z2+ :


2
S⊆V

By the same argument as for the matroid maximization problem, we obtain the following.

Corollary 4.8. For the matroid matching problem, by taking T = Ω(∆c log(n/ǫ)/ǫp),
Algorithm 1 outputs a (2 − ǫ)/3-approximate solution with probability at least 1 − ǫ.
6
Lee, Sviridenko and Vondrák [27] proposed a rounding procedure for a slightly different formulation.
However, since the solution to the present formulation can be easily converted to the Lee et al.’s formulation,
we can use the rounding procedure.

22

4.2.5

Degree Bounded Matroid

Let (V, E) be a hypergraph with |V | = n whose maximum degree is d = maxu∈V |δ(u)|,
and b : E → Z+ give a capacity of each hyperedge. Let M = (V, I) be a matroid whose
rank function is r : 2V → Z+ , and c̃ ∈ ZV+ be a stochastic weight. The degree bounded
matroid problem can be represented as
X
maximize
c̃u xu
u∈V
X
subject to
xu ≤ b(e) (e ∈ E),
(4.24)
u∈e
X
xu ≤ r(S) (S ⊆ V ),
u∈S

x ∈ {0, 1}V .

Király et al. [24] proposed an algorithm that finds a (possibly infeasible) solution whose
objective value is at leastP
the LP-optimal value and which violates each capacity constraint
by at most d − 1. Since u∈V xu ≤ r(V ) =: r, the expected number of revealed elements
is O(rT ).
The only remaining issue is the number of iterations. Since this system has exponentially many constraints, we have to exploit its combinatorial structure to reduce the number
of possibilities. The dual problem is given by
X
X
minimize
b(e)ye +
r(S)zS =: τ (y, z)
subject to

e∈E
X

ye +

e∈δ(u)

S⊆V
X

zS ≥ c̃u

(u ∈ V ),

(4.25)

S⊆V : u∈S
V

2
y ∈ RE
+ , z ∈ R+ .

Since the system is not TDI, we have to discretize the dual variables. We could not prove
the sparsity of z but, by observing the sparsity of y and using the matroid property, we
can see that there exists a good discretization.
V

2
Claim 4.5. Let (y, z) ∈ RE
+ × R+ be an optimal solution to (4.25) with τ (y, z) < µ. Then,
there exists a feasible solution (y ′ , z ′ ) with τ (y ′ , z ′ ) < (1 − ǫ/2)µ whose entries are multiple
of ǫ/2d.

Proof. Let x ∈ RV+ beP
a primal LP-optimal solution. By complementary slackness, ye > 0
only if the constraint u∈e xu ≤ b(e) holds in equality. Thus, by summing up, we have
X
X X
XX
X
b(e) =
xu ≤
xu ≤ d
xu < dµ.
(4.26)
e : ye >0

e : ye >0 u∈e

e∈E u∈e

u∈V

Now we round up each entry of y toPthe minimum multiple of ǫ/2d to obtain y ′ . This
increases objective value at most (ǫ/2d) e : ye >0 b(e) < ǫµ/2. Therefore the objective value
23

of (y ′ , z) is at most (1 − ǫ/2)µ. To discretize z, we consider the minimization problem with
respect to z:
X
minimize
r(S)zS
subject to

S⊆V
X

zS ≥ c̃u −

S⊆V : u∈S

X

ye′ (u ∈ V ).

(4.27)

e∈δ(u)

This problem is the dual of the maximum independent set problem whose cost vector is
a multiple of ǫ/2d. Therefore, by the TDIness of the maximum independent set problem,
there exists an optimal solution z ′ whose entries are multiples of ǫ/2d. Thus, (y ′ , z ′ ) is
feasible by construction and has an objective value of at most (1 − ǫ/2)µ.
As for the other matroid problems, we can assume that supp(z) is a set of flats. For
2V
µ ≥ 1, let us define a set W ⊆ RE
+ × R+ by
n


o
ǫ  E
ǫ
V
W = (y, z) ∈
: τ (y, z) ≤ 1 −
(4.28)
Z+ × Z2+
µ, supp(z) ⊆ FM .
2d
2
By construction, W is an (ǫ, ǫ/2)-witness cover, and we can evaluate its size as follows.

Claim 4.6. |W | = eO(µd log n/ǫ) .
Proof. To evaluate the size of W , we separately count y and z. The number of candidates
for y is evaluated as similar to Lemma 3.1 by distributing 2dµ/ǫ tokens to |E| = O(dn) =
O(n2 ) components, and is bounded by eO(µd log n/ǫ) . The number of candidates for z is
evaluated as similar to Claim 4.3 by counting multisets with weight ǫ/2d, and is bounded
by eO(µd log n/ǫ) . By multiplying these two numbers of candidates, we obtain the required
result.
Therefore, we obtain the following.
Corollary 4.9. For the degree bounded matroid problem with maximum degree d, by
taking T = Ω(∆c d log(n/ǫ)/ǫ2 p), Algorithm 1 outputs a (1 − ǫ)-approximate solution that
violates each constraint at most d − 1 with probability at least 1 − ǫ.

4.3

Stable Set Problems

We finally show applications to stable set problems. In this section, n and m denote the
numbers of vertices and edges, repsectively, in the graph in question.

24

4.3.1

Stable Set in Some Perfect Graphs

We assume that the stability number α (the maximum size of a stable set) is relatively small
to ensure that Algorithm 1 does not reveal all the vertices. By the Turàn theorem [36], the
average degree is required to be relatively large.
Let (V, E) be a graph and c̃ : V → Z+ be a stochastic vertex weight. The maximum
stable set problem can be represented as
X
maximize
c̃u xu
u∈V

subject to xu + xv ≤ 1 ((u, v) ∈ E),
x ∈ {0, 1}V .

(4.29)

The LP relaxation of this system is half-integral. However, this is not helpful because the
number of revealed vertices can be large: there is a solution xu = 1/2 for all u ∈ V , which
corresponds to revealing half of the vertices in expectation.
We instead consider the following formulation, which introduces the clique inequalities:
X
maximize
cu xu
u∈V
X
(4.30)
subject to
xu ≤ 1
(C ∈ C),
u∈C

xu ∈ {0, 1}V ,

where C is the set of maximal cliques. A graph is perfect if the LP relaxation of the above
system is TDI. If we assume that the graph is perfect, Algorithm 1 has an approximation
ratio of (1 − ǫ) with high probability for sufficiently large T , and the number of revealed
vertices is O(αT ) in expectation.
The dual problem is given by
X
minimize
yC
C∈C
X
(4.31)
subject to
yC ≥ cu (u ∈ V ),
C∈C : u∈C
y ∈ RC+ .

If the number of maximal cliques is O(nk ) for some fixed constant k, we immediately see
that the required number of iterations is O(k log(n/ǫ)/ǫp). A perfect graph may have
exponentially many maximal cliques in general, but the following graph classes have at
most polynomially many maximal cliques.
• If a graph is chordal, it has only linear number of maximal cliques.
• If a graph has a bounded clique number (i.e., the
 size of cliques are bounded by a
constant k), the number of cliques is at most nk = O(nk ). This includes a graph
class that can be characterized by forbidden minors and subgraphs.
25

4.3.2

Stable Set in t-Perfect Graphs

Another tractable graph class for the stable set problem is t-perfect graphs. A graph (V, E)
is t-perfect if the relaxation of the following formulation is integral, i.e., it has an integral
optimal solution:
X
maximize
c̃u xu
u∈V

subject to xu + xv ≤1  ((u, v) ∈ E),
X
|C|
xu ≤
(C ∈ C),
2

(4.32)

u∈C

xu ∈ {0, 1}V ,

where C is the set of odd cycles. We assume that the graph is t-perfect. Then, Algorithm
1 has an approximation ratio of (1 − ǫ) with high probability for sufficiently large T , and
the number of revealed vertices is O(αT ).
The only remaining issue is the number of iterations. Since the system (4.32) is not
required
be TDI7 , we have to discretize the dual variables. We use Theorem 3.1. Let

 to
ǫ2
θ = Θ log
n . The corresponding dual problem is given by
minimize

X

X  |C| 

ye +
2
e∈E
C∈C X
X
subject to
ye +

z̃C
zC ≥ c̃u (u ∈ V ),

(4.33)

C∈C : u∈C

e∈δ(u)

C
y ∈ RE
+ , z ∈ R+ .

We regard zC as a multiset in which each odd cycle C contributes θ. Let c1 , . . . , ck be the
sizes of each odd cycles. We then have c1 + · · · + ck < µ/θ. We define the witness cover by
)
(


X
X  |C| 

ǫ
C
µ .
(4.34)
W = (y, z) ∈ θ ZE
:
ye +
zC ≤ 1 −
+ × Z+
2
2
e∈E

C∈C

Claim 4.7. |W | ≤ eO((µ/θ) log n) .
Proof. To evaluate the size of W , we count y and z separately. The number of candidates
for y is clearly eO((µ/θ) log m) (and m = O(n2 )), while the number of candidates for z is
bounded by eO((µ/θ) log n) as the similar argument to Claim 4.1.
Therefore, we obtain the following.
Corollary 4.10. For the t-stable set problem, by taking T = Ω(∆c log n log(n/ǫ)/ǫ3 p),
Algorithm 1 outputs a (1 − ǫ)-approximate solution with probability at least 1 − ǫ.
7

A graph is strongly t-perfect if the system in (4.32) is TDI. Any strongly t-perfect graph is t-perfect,
but the converse is open.

26

5
5.1

Vertex Sparsification Lemma
Vertex Sparsification Lemma

For the (unweighted) stochastic matching problem, Assadi et al. [3] proposed a procedure
called vertex sparsification, which reduces the number of vertices proportional to the maximum matching size µ while approximately preserving any matchings of size ν = ω(1) with
high probability. This procedure is very useful as a preprocessing step for this problem
since it makes n/µ = O(1), and so the required number of iterations becomes constant.
Here, we extend this procedure to an independence system on a k-uniform hypergraph
and improve the result to preserve any independence set with high probability without
assuming ν = ω(1). In next section. we improve the performances of the algorithms for
the bipartite matching problem, k-hypergraph matching problem, and k-column sparse
packing integer programming problem by using this lemma.
In general, sparsification preduces are kinds of kernelization procedure, which is studied
in the area of parametrized complexity [17]. In particular, our and Assadi et al. [3]’s
procedures are similar to the one in [11], which is aimed to for reducing space complexity
of packing problems in streaming setting, but these conduct different analysis and provide
different guarantees.
Let (V, E) be a k-uniform hypergraph and (E, I) be an independence system (which is
a nonempty, downward-closed set system, i.e., I =
6 ∅, and X ⊆ Y ∈ I =⇒ X ∈ I), whose
rank function r : 2E → Z+ is defined by r(S) = max{ |I| : I ⊆ S, I ∈ I }. We focus on the
following special case of the stochastic packing integer programming problem (1.1) in this
section:
X
c̃e xe
maximize
e∈E
X
(5.1)
subject to
xe ≤ r(S) (S ⊆ E),
e∈S

x ∈ {0, 1}E .

Note that the constraint is equivalent to supp(x) ∈ I, and this formulation still includes
the k-column sparse PIP (4.12) (and hence all the matching problems shown in Section
4.1) as follows: let V = {1, . . . , n} and E = {1, . . . , m} such that each hyperedge j ∈ E is
associated with a subset { i ∈ V : aij 6= 0 }P(if the size is less than k, add arbitrary vertices
i with aij = 0), and define I = { S ⊆ E : j∈S aij ≤ bi (∀i ∈ V ) }.
Our procedure is shown in Algorithm 3, which is a kind of color coding. Let s ∈ Z+
be an upper bound on r = r(E), and ǫ, δ ∈ (0, 1) be parameters for the accuracy and
the probability, respectively. It first assigns a random color in {1, . . . , n◦ } to each vertex,
where n◦ = β(k, ǫ, δ)k2 s/δ with β(k, ǫ, δ) = 2eǫ/k log(1/δ)/ǫ. It then returns all “colorful”
hyperedges that consists entirely of differently colored vertices. This yields an independence
system on the color class consisting from n◦ = Θ(s) vertices.
27

Algorithm 3 Vertex sparsification.
2

1:

s
Assign a random color in {1, . . . , β(k,ǫ,δ)k
} to each vertex, where β(k, ǫ, δ) =
2δ
2eǫ/k log(1/δ)
.
ǫ

2:

Return all colorful hyperedges.

Lemma 5.1 (Vertex Sparsification Lemma). Suppose that n ≥ 2k. Then, after Algorithm
3, for any independent set I ∈ I in the original instance, there exists an independent set
I ◦ ⊆ I of size at least (1 − ǫ)|I| in the sparsified instance with probability at least 1 − δ.
Proof. Let ν = |I|. For notational simplicity, we denote by β = β(k, ǫ, δ). We now make
the following case analysis.
Case 1: ν ≤ β (the rank of I is small). If all vertices incident to I have different
colors, the size of I is preserved after the mapping. Since the number of the incident
vertices is at most kν, the probability that this has occurred is at least
 2 2


n◦ (n◦ − 1) · · · (n◦ − kν + 1)
k ν
δν 2
≥ exp − ◦
≥ exp −
≥ e−δ ≥ 1 − δ.
(5.2)
n◦kν
n
βs
Here, the first inequality follows from the falling factorial approximation (Lemma 5.2 below), and the second inequality follows from ν ≤ r ≤ s and ν ≤ β.
Lemma 5.2 (Falling Factorial Approximation).
 2
k
n(n − 1) · · · (n − k + 1)
≥ exp −
.
k
n
n

(5.3)

Proof. Recall that log(1 − x) ≥ −x/(1 − x) for all x ∈ (0, 1). The logarithm of the above is
k−1
X
i=1



i
log 1 −
n



≥−

k−1
X
i=1

k−1

X i
k(k − 1)
k2
i
≥−
=−
≥− .
n−i
n−k
2(n − k)
n

(5.4)

i=1

Case 2: ν ≥ β (the rank of I is large). We further reduce the number of colors by
mapping each color class to {1, . . . , k 2 ν/ǫ}. (Note that k2 ν/ǫ ≤ n◦ since β ≥ 1/ǫ.) We say
that a color class c is good if some vertex in color c is covered by some hyperedge e ∈ I,
and otherwise we say that c is bad.
For each color class c, let Xc be the indicator of the event that c is bad, i.e., Xc = 1
if cPis bad and Xc = 0 otherwise. Then Pr(Xc = 1) = (1 − ǫ/k2 ν)kν ≤ e−ǫ/k . Therefore
E [ c Xc ] ≤ e−ǫ/k k2 ν/ǫ. Since Xc are negatively correlated random variables, we can apply
28

the Chernoff bound [29]:
Pr

X
c

k2 ν 
ǫ
Xc ≥
kν
− 1−
ǫ
k

!

!

ǫ
ǫ2 k 2 ν
Xc ≥ 1 − + 2
= Pr
k k
ǫ
c
!


2
X
ǫ2
−ǫ/k k ν
Xc ≥ 1 + 2 e
≤ Pr
2k
ǫ
c




−ǫ/k ν
−ǫ/k β
≤ exp −ǫe
≤ exp −ǫe
= δ,
2
2
X



(5.5)

where the first inequality follows from (1 + x2 /2)e−x ≤ 1 − x + x2 and the last equality
follows from the definition of β. Therefore, there are at least (1 − ǫ/k)kν good color classes
with high probability.
For each good color class, we select one covered vertex and remove all other vertices.
The number of removed vertices is at most ǫν, so at most ǫν hyperedges in the independent
set are removed. The remaining hyperedges form an independent set of size at least (1 −
ǫ)ν.
Remark 5.1. The second part is a simple extension of Assadi et al. [3]. Since they only
analyzed this case, ν = ω(1) was required.

5.2

Usage of Vertex Sparsification Lemma

Here, we describe how to use the vertex sparsification lemma to improve the performance
of Algorithms 1 and 2. For simplicity, we only describe the result for Algorithm 1, as
Algorithm 2 can be handled using the same argument.
Let (V, E) be a k-uniform hypergraph with |V | = n and |E| = m and (E, I) be an
independence system. We consider the problem (5.1), where we assume the following.
1. There exists an LP-relative α-approximation algorithm.
2. The number of iterations required to guarantee (1 − ǫ)α-approximation with probability at least 1 − δ is bounded by T (log(n/µ), ǫ, δ).
The method is shown in Algorithm 4, where ǫ, δ ∈ (0, 1) be parameters for the accuracy
and the probability, respectively, and cmax = maxj c+
j . We first estimate the maximum size
s of the independent sets such that αs ≤ r ≤ s, which is computed via LP relaxation. We
then apply Algorithm 3 to obtain a sparsified instance, and finally apply Algorithm 1 or 2
with an LP-relative α-approximation algorithm to obtain a solution. We now analyze the
performance of this procedure.
Theorem 5.1. Algorithm 4 finds a (1 − ǫ)α-approximate solution with probability at least
1 − δ.
29

Algorithm 4 Speedup by vertex sparsification.
1: Estimate the size s of maximum independent set such that αs ≤ r ≤ s.
2: Sparsify the instance by Algorithm 3 with accuracy parameter ǫ′ = ǫ/(1 + cmax ) and
probability parameter δ′ = δ/4.
3: Run Algorithm 1 or 2 with an LP-relative α-approximation algorithm by setting T =
T (O(log(k/pαǫ′ δ′ )), ǫ′ , δ′ ).

Proof. Let r = r(E) be the rank of the original independence system and µ̃ the optimal
value of the original instance (5.1), which is a random variable determined by nature. Also,
let r ◦ be the rank of the sparsified instance, and µ̃◦ be the optimal value of the sparsified
instance, which is also a random variable.
Claim 5.1.

Pr r ◦ ≥ (1 − ǫ′ )r ≥ 1 − δ′ ,

Pr µ̃◦ ≥ (1 − cmax ǫ′ )µ̃ ≥ 1 − δ′ .

(5.7)

µ̃◦ ≥ c̃⊤ x◦ ≥ c̃⊤ x − cmax ǫ′ |I| ≥ µ̃ − cmax ǫ′ µ̃,

(5.8)

(5.6)

Proof. The first inequality (5.6) immediately follows from Lemma 5.1, and we focus on the
second (5.7). Fix a realization of c̃, and let x ∈ {0, 1}E be an optimal solution to (5.1) such
that I = supp(x) ∈ I is minimal. By Lemma 5.1, there exists an independent set I ◦ ⊆ I
of size |I ◦ | ≥ (1 − ǫ′ )|I| in the sparsified instance with probability 1 − δ′ . Let x◦ ∈ {0, 1}E
be the vector with supp(x◦ ) = I ◦ , whose restriction to the sparsified hyperedge set is a
feasible solution to the sparsified instance. We then have

where the last inequality follows from the minimality of I = supp(x) (for each j ∈ I, we
must have c̃j ≥ 1, and hence µ̃ = c̃⊤ x ≥ supp(x) = |I|).
By Claim 5.1, we have r ◦ ≥ (1 − ǫ′ )r and µ̃◦ ≥ (1 − cmax ǫ′ )µ̃ with probability at least
1 − 2δ′ . Under this event, by using Algorithm 1 in Line 3 of Algorithm 4, we obtain a
solution whose objective value is at least (1 − ǫ′ )µ̃◦ ≥ (1 − (cmax + 1)ǫ′ )µ̃ = (1 − ǫ)µ̃ with
probability at least 1 − δ′ (and hence with probability at least 1 − 3δ′ in total).
The remaining issue is the number of iterations. That is, for β ′ = β(k, ǫ′ , δ′ ) =
′ /k
ǫ
2e
log(1/δ′ )/ǫ′ and n◦ = β ′ k2 s/δ′ , we prove


k
n◦
,
(5.9)
log ◦ = O log
µ̃
pαǫ′ δ′
with probability at least 1 − δ′ , which implies that we succeed with probability at least
1 − 4δ′ = 1 − δ through Algorithm 4. We make a case analysis.

30

Case 1. r ◦ ≥ 8 log(1/δ′ )/p (the rank of the sparsified instance is large). We evaluate the objective value of the independent set in the sparsified instance that corresponds
to the maximum independent set in the original instance. Since each element in the sparsified independent set contributes at least 1 with probability at least p, we can apply the
Chernoff bound
!


r◦
◦
◦
X
pr
pr
◦
Pr µ̃◦ ≥
≥ 1 − e−pr /8 ≥ 1 − δ′
(5.10)
Xi ≥
≥ Pr
2
2
i=1

where Xi (i = 1, . . . , r ◦ ) are i.i.d. random variables following the Bernoulli distribution
with probability p. Under this event (µ̃◦ ≥ pr ◦ /2), we have
′

4n◦
4β ′ k2
2n◦
4n◦
8eǫ /k log(1/δ′ )
n◦
≤
=
≤
≤
=
,
µ̃◦
pr ◦
pr
pαs
pαδ′
pαǫ′ δ′

(5.11)

where the second inequality follows from r ◦ ≥ (1 − ǫ′ )r ≥ r/2 (because ǫ′ = ǫ/(1 + cmax ) ≤
′
1/2), and the third from r ≥ αs. Since eǫ /k = O(1) and log(1/δ′ ) ≤ 1/δ′ , we have (5.9).
Case 2. r ◦ ≤ 8 log(1/δ′ )/p (the rank of the sparsified instance is small).
n◦
β ′ k2 r
2β ′ k2 r ◦
16β ′ k2 log(1/δ′ )
◦
≤
n
≤
≤
≤
,
µ̃◦
αδ′
αδ′
pαδ′

We have
(5.12)

where the first inequality follows from µ̃◦ ≥ 1 (because it is an integer with µ̃◦ ≥ (1 −
ǫ′ cmax )µ̃ > 0), the second from r ≥ αs, and the third from r ◦ ≥ r/2. This leads to (5.9)
similarly in Case 1.
The sizes of witness covers of bipartite matching, k-hypergraph matching, and kcolumn-sparse packing integer programming depend on n/µ. Thus these are improved
by using this technique.
Corollary 5.1. For the bipartite matching problem with cj = O(1) for all j, there is an
algorithm that conducts O(log(1/ǫp)/ǫp) queries per vertex and finds (1 − ǫ)-approximate
solution with probability at least 1 − ǫ.
Corollary 5.2. For the k-hypergraph matching problem with cj = O(1) for all j, there
is an algorithm that conducts O(k(log(k/ǫp) + 1/ǫ)/ǫp) queries per vertex and finds (1 −
ǫ)/(k − 1 + 1/k)-approximate solution with probability at least 1 − ǫ.
Corollary 5.3. For the k-column sparse packing integer programming problem with
cj = O(1), bi = O(1), and Aij = O(1) for all i, j, there is an algorithm that conducts
O(k(log(k/ǫp) + 1/ǫ)/ǫp) queries per vertex and finds (1 − ǫ)/2k-approximate solution with
probability at least 1 − ǫ.
31

Acknowledgment
The authors thank anonymous reviewers for their valuable comments. This work was
supported by JSPS KAKENHI Grant Numbers 16H06931 and 16K16011.

References
[1] Marek Adamczyk. Improved analysis of the greedy algorithm for stochastic matching.
Information Processing Letters, 111(15):731–737, 2011.
[2] Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Mathematics of Operations Research, 41(3):1022–1038, 2016.
[3] Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with
(very) few queries. In Proceedings of the 2016 ACM Conference on Economics and
Computation, pages 43–60. ACM, 2016.
[4] Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem:
Beating half with a non-adaptive algorithm. Proceedings of the 2017 ACM Conference
on Economics and Computation, pages 99–116, 2017.
[5] Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri
Rudra. When lp is the cure for your matching woes: Improved bounds for stochastic
matchings. Algorithmica, 63(4):733–762, 2012.
[6] Soheil Behnezhad and Nima Reyhani. Almost optimal stochastic weighted matching
with few queries. arXiv preprint arXiv:1710.10592, 2017.
[7] Avrim Blum, John P Dickerson, Nika Haghtalab, Ariel D Procaccia, Tuomas Sandholm, and Ankit Sharma. Ignorance is almost bliss: Near-optimal stochastic matching
with few queries. In Proceedings of the 2015 ACM Conference on Economics and Computation, pages 325–342. ACM, 2015.
[8] Avrim Blum, Anupam Gupta, Ariel Procaccia, and Ankit Sharma. Harnessing the
power of two crossmatches. In Proceedings of the 2013 ACM conference on Electronic
Commerce, pages 123–140. ACM, 2013.
[9] Yuk Hei Chan and Lap Chi Lau. On linear and semidefinite programming relaxations
for hypergraph matching. In Proceedings of the 21st Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1500–1511, 2010.
[10] Ning Chen, Nicole Immorlica, Anna R Karlin, Mohammad Mahdian, and Atri Rudra.
Approximating matches made in heaven. In Proceedings of the 2009 International
Colloquium on Automata, Languages, and Programming, pages 266–278. Springer,
2009.
32

[11] Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi,
Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via
sampling with applications to finding matchings and related problems in dynamic
graph streams. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1326–1344. Society for Industrial and Applied
Mathematics, 2016.
[12] Kevin Costello, Prasad Tetali, and Pushkar Tripathi. Stochastic matching with commitment. Automata, Languages, and Programming, pages 822–833, 2012.
[13] William H Cunningham and AB Marsh. A primal algorithm for optimum matching.
Polyhedral Combinatorics, pages 50–72, 1978.
[14] Brian C Dean, Michel X Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the 16th Annual ACM-SIAM
Symposium on Discrete Algorithms, pages 395–404, 2005.
[15] Brian C Dean, Michel X Goemans, and J Vondrdk. Approximating the stochastic
knapsack problem: The benefit of adaptivity. In Proceedings of the 45th Annual IEEE
Symposium on Foundations of Computer Science, pages 208–217, 2004.
[16] John P Dickerson and Tuomas Sandholm. Organ exchanges: A success story of ai in
healthcare. 2016.
[17] Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer
Science & Business Media, 2012.
[18] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. Edited by G.
Goos, J. Hartmanis, and J. van Leeuwen, 11, 1970.
[19] Eugene Egerváry. On combinatorial properties of matrices. 1931.
[20] Dion Gijswijt and Gyula Pap. An algorithm for weighted fractional matroid matching.
Journal of Combinatorial Theory, Series B, 103(4):509–520, 2013.
[21] Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Proceedings of the 2013 International Conference on Integer Programming
and Combinatorial Optimization, pages 205–216, 2013.
[22] Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and xos functions. In Proceedings of the 28th Annual ACMSIAM Symposium on Discrete Algorithms, pages 1688–1702. SIAM, 2017.
[23] Cor A. J. Hurkens and Alexander Schrijver. On the size of systems of sets every t of
which have an sdr, with an application to the worst-case ratio of heuristics for packing
problems. SIAM Journal on Discrete Mathematics, 2(1):68–72, 1989.
33

[24] Tamás Király, Lap Chi Lau, and Mohit Singh. Degree bounded matroids and submodular flows. Combinatorica, 32(6):703–720, 2012.
[25] Stavros G Kolliopoulos and Neal E Young. Approximation algorithms for covering/packing integer programs. Journal of Computer and System Sciences, 71(4):495–
505, 2005.
[26] D Kőnig. Graphs and matrices. Math. Fiz. Lapok, 38:116–119, 1931.
[27] Jon Lee, Maxim Sviridenko, and Jan Vondrák. Matroid matching: the power of local
search. SIAM Journal on Computing, 42(1):357–379, 2013.
[28] Marco Molinaro and R Ravi.
arXiv:1110.0990, 2011.

The query-commit problem.

arXiv preprint

[29] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring
via an extension of the Chernoff–Hoeffding bounds. SIAM Journal on Computing,
26(2):350–368, 1997.
[30] Ojas Parekh. Iterative packing for demand and hypergraph matching. In Proceedings
of the 2011 International Conference on Integer Programming and Combinatorial Optimization, pages 349–361, 2011.
[31] Ojas Parekh and David Pritchard. Generalized hypergraph matching via iterated
packing and local ratio. In International Workshop on Approximation and Online
Algorithms, pages 207–223. Springer, 2014.
[32] Prabhakar Raghavan and Clark D Tompson. Randomized rounding: a technique for
provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987.
[33] Alvin E Roth, Tayfun Sönmez, and M Utku Ünver. Kidney exchange. The Quarterly
Journal of Economics, 119(2):457–488, 2004.
[34] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume
24. 2003.
[35] F Bruce Shepherd and Adrian Vetta. The demand-matching problem. Mathematics
of Operations Research, 32(3):563–578, 2007.
[36] Paul Turán. On the theory of graphs. In Colloquium Mathematicae, volume 3, pages
19–30. Institute of Mathematics Polish Academy of Sciences, 1954.
[37] John H Vande Vate. Fractional matroid matchings. Journal of Combinatorial Theory,
Series B, 55(1):133–145, 1992.

34

