Algorithms to Approximate Column-Sparse Packing Problems
Brian Brubach∗, Karthik A. Sankararaman†, Aravind Srinivasan‡, and Pan Xu§

arXiv:1711.02724v4 [cs.DS] 11 Dec 2017

Department of Computer Science, University of Maryland, College Park, MD 20742, USA

Abstract
Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems.
As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations
for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic
k-set packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a
major integrality-gap conjecture of Füredi, Kahn and Seymour on hypergraph matching (Combinatorica,
1993).

This is a full version of the paper that appeared in SODA-2018. This version improves the presentation and fixes some typos.

Acknowledgements. We would like to thank David Harris for pointing out the equivalence between
Conjecture 2 and Conjecture 1. We also thank him for pointing out useful prior results on graph coloring in parallel and distributed settings. We would like to thank the anonymous reviewers for valuable
comments on this paper.

∗
Email: bbrubach@cs.umd.edu
Supported in part by NSF Awards CNS 1010789 and CCF 1422569.
†
Email: kabinav@cs.umd.edu
Supported in part by NSF Awards CNS 1010789 and CCF 1422569.
‡
Email: srin@cs.umd.edu
Supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc.
§
Email: panxu@cs.umd.edu
Supported in part by NSF Awards CNS 1010789 and CCF 1422569.

1 Introduction
Column-sparse packing problems arise in numerous contexts (e.g., [2, 15, 12, 13, 47, 16, 25, 24, 52, 39,
46]). We present two unifying ideas (attenuation and multiple-chances) to obtain improved approximation
algorithms and/or (constructive) existence results for some well-known families of such problems. These
two unifying ideas help better handle the contention resolution [32] that is implicit in such problems. As
three main examples, we attain the integrality gap (up to lower-order terms) for known LP relaxations for
k-column sparse packing integer programs (k -CS-PIP: Bansal et al. [13]) and stochastic k-set packing
(SKSP: Bansal et al. [12]), and go “half the remaining distance” to optimal for a major integrality-gap
conjecture of Füredi, Kahn and Seymour on hypergraph matching [39].
Letting R+ denote the set of non-negative reals, a general Packing Integer Program (PIP) takes the
form:
max {f (x) | A · x ≤ b, x ∈ {0, 1}n } ,

m×n
; (1)
where b ∈ Rm
+ , and A ∈ R+

here A · x ≤ b means, as usual, that A · x ≤ b coordinate-wise. Furthermore, n is the number of
variables/columns, m is the number of constraints/rows, A is the matrix of sizes with the j th column representing the size vector SIj ∈ Rm
+ of item j, b is the capacity vector, and f is some non-decreasing function
(often of the form w · x, where w is a nonnegative vector of weights). The items’ “size vectors” SIj can be
deterministic or random. PIPs generalize a large class of problems in combinatorial optimization. These
range from optimally solvable problems such as classical matching to much harder problems like independent set which is NP-Hard to approximate to within a factor of n1−ǫ [70].
A k-column sparse packing program (k -CS-PP) refers to a special case of packing programs wherein
each size vector SIj (a column of A) takes positive values only on a subset C(j) ⊆ [m] of coordinates with
|C(j)| ≤ k. The k -CS-PP family captures a broad class of packing programs that are well studied such as
k-column sparse packing integer programs (k -CS-PIP), k-uniform hypergraph matching, stochastic matching, and stochastic k-set packing (SKSP). While we primarily focus on programs with linear objectives,
some of these approaches can be extended to monotone submodular objectives as well from prior work
(e.g., [13], [32]).
We show randomized-rounding techniques (including non-uniform attenuation, multiple chances) that,
along with the “nibble method” [4, 63] in some cases, yield improved results for some important families
of Packing Integer Programs (PIPs). In the case of k -CS-PIP and SKSP, we show asymptotically optimal
bounds matching the LP integrality gap (as a function of the column-sparsity k, which is our asymptotic
parameter). For hypergraph matching, we make progress “half the remaining way” towards meeting a
classic conjecture of Füredi et al. [39]. Additionally, we show a simple application of simulation-based
attenuation to obtain improved ratios for the Unsplittable Flow Problem on trees (UFP-TREES: Chekuri
et al. [30]) with unit demands and submodular objectives, a problem which admits a natural packing-LP
relaxation.

1.1 Preliminaries and Main Results
The natural LP relaxation is as follows (although additional valid constraints are necessary for k -CS-PIP [13]):
max{w · x : A · x ≤ b, x ∈ [0, 1]n }

(2)

Typically, a rounding algorithm takes as input an optimal solution x ∈ [0, 1]n to LP (2) – or one of
its relatives – and outputs an integral X ∈ {0, 1}n which is feasible for PIP (1) such that the resultant
1

approximation ratio, E[w·X]
w·x , is maximized. Note that E[w · X] is the expected weight of the solution over
all randomness in the algorithm and/or the problem itself. For a general weight vector w, we often seek to
E[X ]
maximize minj:xj 6=0 xj j , as the usual “local” strategy of maximizing the approximation ratio. As notation,
we will denote the support of X as the set of rounded items. We say item j participates in constraint i if and
only if Aij 6= 0. We say that a variable is safe to be rounded to 1 if doing so would not violate any constraint
conditional on the variables already rounded; we call it unsafe otherwise.
k-Column Sparse Packing Integer Programs (k -CS-PIP). Suppose we have n items and m constraints.
Each item j ∈ [n] has a weight wj and a column aj ∈ [0, 1]m . Suppose we have a capacity vector b = 1
(this is w.l.o.g., see e.g., Bansal et al. [13]) and our goal is to select a subset of items such that the total
weight is maximized while no constraint is violated. In addition, we assume each column aj has at most k
non-zero entries. (The important special case where for all j, aj lies in {0, 1}m – and has at most k non-zero
entries – is the classic k-set packing problem; it is NP-hard to approximate within o(k/ log k) [44]. This
special case is generalized in two ways below: by allowing stochasticity in stochastic k-set packing, and
by allowing the column-sparsity k to vary across columns as in hypergraph matching.) Observe that this
problem (i.e., k -CS-PIP) can be cast as a special case of PIP shown in (1) with the j th column of A being
A[j] = aj . The resultant LP relaxation is as follows (just as in Bansal et al. [13], we will ultimately use a
stronger form of this LP relaxation which incorporates additional valid constraints; see (7) in Section 2.1).
max{w · x : A · x ≤ 1, x ∈ [0, 1]n } where A[j] = aj

(3)

For general PIPs, the best-known approximation bounds are shown in Srinivasan [67]. The problem of
k -CS-PIP, in its full generality, was first considered by Pritchard [61] and followed by several subsequent
works such as Pritchard and Chakrabarty [62] and Bansal et al. [13]. Chekuri et al. [32] defined a contention
resolution framework for submodular objectives and showed how the previous algorithms for k -CS-PIP
fit into such a framework (and hence, extending the k -CS-PIP algorithms to non-negative submodular
objectives by losing a constant factor in approximation)1 .
Our main result for this problem is described in Theorem 1. Bansal et al. [13] showed that the stronger
LP (which adds additional valid constraints to the natural LP relaxation) has an integrality gap of at least
2k − 1. We consider the same LP, and hence our result shown in Theorem 1 is asymptotically optimal
w.r.t. this LP. The previous best known results for this problem were a factor of ek + o(k) due to Bansal
et al. [13], a factor of O(k2 ) independently due to Chekuri et al. [26] 2 and Pritchard and Chakrabarty [62],
and a factor of O(2k · k2 ) due to Pritchard [61].
Theorem 1. There exists a randomized rounding algorithm for k -CS-PIP with approximation ratio at most
2k + o(k) for linear objectives.
Corollary 1. There exists a randomized rounding algorithm for k -CS-PIP with approximation ratio at
most (2k + o(k))/ηf for non-negative submodular objectives, where ηf is the approximation ratio for
max{F (x) : x ∈ PI ∩ {0, 1}n } (here, F (x) is the multi-linear extension of the sub-modular function f and
PI is the k -CS-PIP polytope); ηf = 1 − 1/e and ηf = 0.385 in the cases of non-negative monotone and
non-monotone submodular functions respectively3 .
1

In [13], the authors also show extensions to non-negative monotone submodular objectives.
Note that this work is cited in [13].
3
To keep consistent with prior literature, we state all approximation ratios for sub-modular maximization (i.e., ηf ) as a value
less than 1. This is in contrast to the approximation ratios defined in this paper where the values are always greater than 1
2

2

Stochastic k-Set Packing (SKSP). The Stochastic k-Set Packing problem was first introduced in Bansal
et al. [12] as a way to generalize several stochastic-optimization problems such as Stochastic Matching4 .
The problem can be defined formally as follows. Suppose we have n items and that each item j has a
random non-negative weight Wj and a random m-dimensional size vector SIj ∈ {0, 1}m . The random
variables {Rj := (Wj , SIj ) : j ∈ [n]} are mutually independent5 . Each random vector Rj ∈ R+ × {0, 1}m
is drawn from some probability distribution: our algorithm only needs to know the values of ui,j := E[SIi,j ]
for all i, j – where SIi,j denotes the ith component of SIj – and wj := E[Wj ]. Moreover, for each item j,
there is a known subset C(j) ⊆ [m] of at most k coordinates such that SIi,j can be nonzero only if i ∈ C(j):
all coordinates in [m] \ C(j) will have value zero with probability 1. We are given a capacity vector b ∈ Zm
+.
The algorithm proceeds in multiple steps. At each step, we consider any one item j that has not been
considered before, and which is safe with respect to the current remaining capacity, i.e., adding item j to the
current set of already-added items will not cause any capacity constraint to be violated regardless of what
random SIj materializes.6 Upon choosing to probe j, the algorithm observes its size realization and weight,
and has to irrevocably include j. The task is to sequentially probe some subset of the items such that the
expected total weight of items added is maximized.
Let w denote (w1 , . . . , wn ) and xj denote the probability that j is added in the OPT solution. Bansal
et al. [12] introduced the following natural LP to upper bound the optimal performance.
max{w · x : A · x ≤ b, x ∈ [0, 1]n } where A[i, j] = ui,j

(4)

The previous best known bound for SKSP was 2k+o(k) due to Bansal et al. [12]. Our main contribution
(Theorem 2) is to improve this bound to k + o(k), a result that is again asymptotically optimal w.r.t. the
natural LP (4) considered (Theorem 1.3 from [39]).
Theorem 2. There exists a randomized rounding algorithm achieving an approximation ratio of k + o(k)
for the stochastic k-set packing problem, where the “o(k)” is a vanishing term when k → ∞.
Hypergraph Matching. Suppose we have a hypergraph H = (V, E) with |V| = m and |E| = n. (This is
the opposite of the usual graph notation, but is convenient for us since the LP here has |V| constraints and
|E| variables.) Each edge e ∈ E has a weight we . We need to find a subset of edges with maximum total
weight such that every pairwise intersection is empty (i.e., we obtain a hypergraph matching). Observe that
the problem of finding a maximum weighted hypergraph matching can be cast as a special case of PIP. Let
w = (we ) and e ∈ {0, 1}m be the canonical (characteristic-vector) representation of e. Then the natural LP
relaxation is as follows:
max{w · x : A · x ≤ 1, x ∈ [0, 1]n } where A[j] = ej

(5)

Note that in these natural IP and LP formulations, the number of vertices in an edge e, ke = |e|, can be
viewed as the column-sparsity of the column associated with e. Thus, this again broadly falls into the class
of column-sparse packing programs. For general hypergraphs, Füredi et al. [39] presented the following
well-known conjecture.
Conjecture 1 (Füredi et al. [39]). For any hypergraph H = (V, E) and a weight vector w = (we ) over all
edges, there exists a matching M such that


P
1
(6)
k
−
1
+
e
e∈M
ke we ≥ OPT(H, w)
4

Here, we use the definition from the journal version [12]; the conference version of [12] defines the problem slightly differently.
Note that Wj can be correlated with SIj .
6
This is called the safe-policy assumption. This allows us to handle the correlations between Wj and coordinates of SIj . A
detailed discussion of this model can be found in [12].
5

3

where ke denotes the number of vertices in hyperedge e and OPT(H, w) denotes an optimal solution to the
LP relaxation (5) of hypergraph matching.
The function “ke − 1 + k1e ” is best-possible in the sense that certain hypergraph families achieve it [39].
We generalize Conjecture 1 slightly:
Conjecture 2 (Generalization of Conjecture 1). For any given hypergraph H = (V, E) with notation as in
Conjecture 1, let x = (xe : e ∈ E) denote a given optimal solution to the LP relaxation (5). Then: (i) there
is a distribution D on the matchings of H such that for each edge e, the probability that it is present in a
xe
, and (ii) D is efficiently samplable.
sample from D is at least ke −1+1/k
e
Part (i) of Conjecture 2 immediately implies Conjecture 1 via the linearity of expectation. In fact, Part
(i) of Conjecture 2 and Conjecture 1 are equivalent which can be shown using a LP-duality argument for the
standard LP for computing the fractional chromatic number.
Füredi et al. [39] gave (non-constructive) proofs for Conjecture 1 for the three special cases where the
hypergraph is either uniform, intersecting, or uniformly weighted. Chan and Lau [24] gave an algorithmic
proof of Conjecture 1 for k-uniform hypergraphs, by combining the iterative rounding method and the fractional local ratio method. Using similar techniques, Parekh [58] and Parekh and Pritchard [59] generalized
this to k- uniform b-hypergraph matching. We go “half the remaining distance” in resolving Conjecture 2
for all hypergraphs, and also do so algorithmically: the work of Bansal et al. [12] gives “ke + 1” instead of
the target ke − 1 + 1/ke in Conjecture 2, and we improve this to ke + O(ke · exp(−ke )).
Theorem 3. There exists an efficient algorithm to generate a random matching M for a hypergraph such
xe
that each edge e is added in M with probability at least ke +o(1)
, where {xe } is an optimal solution to the
standard LP (5) and where the o(1) term is O(ke exp(−ke )), a vanishing term when ke → ∞.
UFP-TREES with unit demands. In this problem, we are given a tree T = (V, E) with each edge e
having an integral capacity ue . We are given k distinct pairs of vertices (s1 , t1 ), (s2 , t2 ), . . . , (sk , tk ) each
having unit demand. Routing a demand pair (si , ti ) exhausts one unit of capacity on all the edges in the
path. With each demand pair i, there is an associated weight wi ≥ 0. The goal of the problem is to choose a
subset of demand pairs to route such that no edge capacity is violated, while the total weight of the chosen
subset is maximized. In the non-negative submodular version of this problem, we are given a non-negative
submodular function f over all subsets of demand pairs, and aim to choose a feasible subset that maximizes
f . This problem was introduced by Chekuri et al. [30] and the extension to submodular version was given by
Chekuri et al. [32]. We show that by incorporating simple attenuation ideas, we can improve the analysis of
the previous best algorithm for the Unsplittable Flow Problem in Trees (UFP-TREES) with unit demands
and non-negative submodular objectives.
Chekuri et al. [32] showed that they can obtain an approximation of 27/ηf , where ηf is the approximation ratio for maximizing a non-negative submodular function, via their contention-resolution scheme
(henceforth abbreviated as CR schemes)7 . We improve their 1/27-balanced CR scheme to a 1/8.15-balanced
CR scheme via attenuation and hence achieve an approximation of 8.15/ηf for non-negative sub-modular
objectives.
Theorem 4. There exists a 8.15/ηf -approximation algorithm to the UFP-TREES with unit demands and
non-negative submodular objectives.
7

Please see Section 2.3 for formal definitions of CR schemes.

4

Extension to submodular objectives. Chekuri et al. [32] showed that given a rounding scheme for a PIP
with linear objectives, we can extend it to non-negative submodular objectives by losing only a constant
factor, if the rounding scheme has a certain structure (see Theorem 7, due to [32]). Our improved algorithm
for k -CS-PIP and UFP-TREES admits this structure and hence can be extended to non-negative submodular functions. See Section B in the Appendix for the required background on submodular functions.
A simple but useful device that we will use often is as follows.
Simulation-based attenuation. We use the term simulation throughout this paper to refer to Monte Carlo
simulation and the term simulation-based attenuation to refer to the simulation and attenuation techniques
as shown in [2] and [19]. At a high level, suppose we have a randomized algorithm such that for some
event E (e.g., the event that item j is safe to be selected into the final set in SKSP) we have Pr[E] ≥ c,
then we modify the algorithm as follows: (i) We first use simulation to estimate a value Ê that lies in the
range [Pr[E], (1 + ǫ) Pr[E]] with probability at least 1 − δ. (ii) By “ignoring” E (i.e., attenuation, in a
problem-specific manner) with probability ∼ c/Ê, we can ensure that the final effective value of Pr[E] is
arbitrarily close to c, i.e., in the range [c/(1 + ǫ), c] with probability at least 1 − δ. This simple idea of
attenuating the probability of an event to come down approximately to a certain value c is what we term
simulation-based attenuation. The number of samples needed to obtain the estimate Ê is Θ( cǫ12 · log( 1δ ))
via a standard Chernoff-bound argument. In our applications, we will take ǫ = 1/poly(N ) where N is the
problem-size, and the error ǫ will only impact lower-order terms in our approximations.

1.2 Our Techniques
In this section, we describe our main technical contributions of the paper and the ingredients leading up to
them.
Achieving the integrality gap of the LP of [13] for k -CS-PIP. Our first main contribution in this paper is
to achieve the integrality gap of the strenghthened LP of [13] for k -CS-PIP, up to lower-order terms: we
improve the ek + o(k) of [13] to 2k + o(k). We achieve this by following the same overall structure as in
[13] and improve the alteration steps using randomization. We view the alteration step as a question on an
appropriately constructed directed graph. In particular, a key ingredient in the alteration step answers the
following question. “Suppose we are given a directed graph G such that the maximum out-degree is bounded
by an asymptotic parameter d. Find a random independent set I in the undirected version of this graph such
that every vertex is added into I with probability at least 1/(2d)−o(1/d)”. It turns out that this question can
be answered by looking at the more-general question of finding a good coloring of the undirected version
of this graph. The key idea here is to “slow down” the contention-resolution approach of [13], leading
to Theorem 1. However, motivated by works that obtain strong “negative correlation” properties – e.g.,
the papers [31, 60] obtain negative cylindrical correlation8 and the even-stronger negative association for
rounding in matroid polytopes – we ask next if one can achieve this for k -CS-PIP. (It is well-known that
even negative cylindrical correlation yields Chernoff-type bounds for sums of random variables [57]; we use
this in Section 5.) We make progress toward this in Theorem 6.
Achieving the integrality gap of the natural LP for SKSP via a “multiple chances” technique. Our
second contribution in is to develop an algorithm that achieves the integrality gap of k + o(k) for SKSP,
improving on the 2k of [12]. To achieve this, we introduce the “multiple-chances” technique. We will
now informally describe this technique, which is motivated by the powerful “nibble” idea from probabilistic
combinatorics (see, e.g., Ajtai, Komlós, and Szemerédi [4] and Rödl [63]).
8

This is sometimes simply called “negative correlation”.

5

The current-best ratios for many special cases of k -CS-PP are Θ(k); e.g., ek+o(k) for k -CS-PIP [13],
the optimal approximation ratio (w.r.t. the integrality gap) of k − 1 + 1/k for k-uniform hypergraph matching [24], or the 2k-approximation for SKSP [12]. Thus, many natural approaches involve sampling items
with a probability proportional to 1/k. Consider a k -CS-PP instance with budget b. Suppose we have a
randomized algorithm ALG which outputs a solution SOL wherein each item j is added SOL with probability exactly equal to xj /(ck) for some constant c > 0.9 After running ALG, the expected usage of each
budget i is bi /(ck); this follows directly from the budget constraint in the LP. This implies that after running
ALG, we have only used a tiny fraction of the whole budget, in expectation. Thus, we may run ALG again
on the remaining items to further improve the value/weight of SOL. Hence, an item that was previously
not chosen, receives a “second chance” to be rounded up and included in the solution. The observation
that only a tiny fraction of the budget is used can be made after running ALG for a second time as well.
Hence, in principle, we can run ALG multiple times and we call the overarching approach a multiple chance
algorithm. The analysis becomes rather delicate as we run for a large number of iterations in this manner.
“Half the remaining distance” toward resolving the FKS conjecture and non-uniform attenuation approach. Our third contribution is in making significant progress on the well-known Conjecture 1 due to
Füredi, Kahn and Seymour. To achieve this, we introduce a technique of non-uniform attenuation. A common framework for tackling k -CS-PP and related problems is random permutation followed by sampling
via uniform attenuation: follow a random order π on the items and add each item j with probability αxj
whenever it is safe, where xj is an optimal solution to an appropriate LP and α is the attenuation factor.
Typically α is a parameter fixed in the analysis to get the best ratio (e.g., see the SKSP algorithm in Bansal
et al. [12]). This method is called uniform attenuation, since all items share the same attenuation factor α.
An alternative strategy used previously is that of weighted random permutations (see, e.g., Adamczyk
et al. [2] and Baveja et al. [15]): instead of using a uniformly-random permutation, the algorithm “weights”
the items and permutes them non-uniformly based on their xj values. We introduce a notion of non-uniform
attenuation, which approaches the worst-case scenario in a different manner. We still stay within the regime
of uniform permutations but will attenuate items non-uniformly, based on their xj values; a careful choice
of attenuation function is very helpful here, as suggested by the optimization problem (12). This is a key
ingredient in our improvement.

1.3 Other Related Work
In this subsection, we list the related work not mentioned in previous sections and yet closely related to
the problems we study. Note that packing programs, submodular maximization, and their applications to
approximation algorithms have a vast literature. Our goal here is to list some papers in closely relevant areas
and this is by no means an exhaustive list of references in each of these closely-aligned areas.
For k -CS-PIP, related problems have been studied in discrepancy theory. In such problems, we have
a k-column sparse LP and we want to round the fractional solution such that the violation (both above and
below) of any constraint is minimized. This study started with the famous work of Beck and Fiala [17] and
some of the previous work on k -CS-PIP (e.g., [61]) used techniques similar to Beck and Fiala. There has
been a long line of work following Beck and Fiala, including [66, 7, 14, 55, 64, 43, 11, 53, 9]. One special
case of k -CS-PIP is the k-set packing problem. Many works including [45, 5, 25, 18] studied this problem
with [18] giving the best approximation of (k + 1)/2 + ǫ for this problem. Closely related to k -CS-PIP
is the notion of column-restricted packing introduced by Kolliopoulos and Stein [47]. Many works have
9

Note that given an algorithm which adds each item with probability at least xj /(ck), we can use Monte Carlo simulation and
attenuation techniques similar to [32, 2, 19] to get an algorithm which adds each item with probability essentially equal to xj /(ck).

6

studied this version of packing programs, including [30, 27, 16].
Similar to Bansal et al. [13], our algorithms also extend to submodular objective functions. In particular,
we use tools and techniques from Calinescu et al. [22] and Chekuri et al. [32] for both k -CS-PIP and the
UFP problem on trees. Monotone sub-modular function maximization subject to k-sparse constraints has
been studied in the context of k-partition matroids, k-knapsacks, and the intersection of k partition matroids
in many works including [38, 51, 69, 50]. Beyond the monotone case, there are several algorithms for the
non-negative sub-modular maximization problem including [37, 28, 21, 36, 20].
Stochastic variants of PIPs have also been previously studied. Baveja et al. [15] considered the following stochastic setting of k-uniform hypergraph matching: the algorithm has to probe edge e to check its
existence; each edge e is associated with a probability 0 < pe ≤ 1 with which it will be present (independently of other edges) on being probed; the task is to sequentially probe edges such that the expected total
weight of matching obtained is maximized. The stochastic version of hypergraph matching can be viewed
as a natural generalization of stochastic matching (e.g., Bansal et al. [12]) to hypergraphs. The work of [15]
gave an (k + ǫ + o(1))–approximation algorithm for any given ǫ > 0 asymptotically for large k. Other work
on stochastic variants of PIPs includes [33, 34, 54, 3, 42, 1, 41].
Later in this paper, we show yet another application of attenuation: UFP-TREES with unit demands.
This problem is a more specific version of column-restricted packing problems mentioned previously. The
Unsplittable Flow Problem in general graphs and its various specializations on different kinds of graphs has
been extensively studied. Some of these works include [46, 65, 40, 48, 29, 8, 6, 49, 23, 10, 35].

1.4 Outline
In Section 2, we present a randomized rounding algorithm for k -CS-PIP using randomized alteration techniques. We analyze this algorithm to prove Theorem 1 and show an extension to submodular objectives. In
Section 3, we apply second-chance techniques to SKSP. After analyzing this algorithm, we show how it
can be extended to multiple chances, yielding the improved result of Theorem 2. In Section 4, we present an
algorithm for hypergraph matching and analyze it to prove Theorem 3, making progress toward Conjecture 2
(and by extension Conjecture 1). In Section 5, we show how attenuation can lead to an improved contention
resolution scheme for UFP-TREES, proving Theorem 4. We end with a brief conclusion and discussion of
open problems in Section 6. All proofs from main section can be found in Section 7. Appendix A contains
a few useful technical lemmas used in this paper while Appendix B gives a self-contained background on
submodular functions.

2 k-Column Sparse Packing
We describe a rounding algorithm for k -CS-PIP, which achieves the asymptotically optimal approximation
ratio of (2k + o(k)) with respect to the strengthened LP shown in Bansal et al. [13] (see (7) in Section 2.1).
Theorem 6 then develops a near-negative-correlation generalization of this result.
Recall that we have a k-sparse matrix A ∈ [0, 1]m×n and a fractional solution x ∈ [0, 1]n such that
A·x ≤ 1. Our goal is to obtain an integral solution X ∈ {0, 1}n (possibly random) such that A·X ≤ 1 and
such that the expected value of the objective function w · X is “large”. (We will later extend this to the case
where the objective function f (X) is monotone submodular.) At a very high level, our algorithm performs
steps similar to the contention-resolution scheme defined by Chekuri et al. [32]; the main contribution is
in the details10 . We first perform an independent-sampling step to obtain a random set R of variables; we
10

We would like to point out that the work of [13] also performs similar steps and fits into the framework of [32].

7

then conduct randomized alterations to the set R to obtain a set of rounded variables that are feasible for the
original program with probability 1. Note that the work of [13] uses deterministic alterations. Moving from
deterministic alteration to careful randomized alteration, as well as using a much-less aggressive uniform
attenuation in the initial independent sampling, yield us the optimal bound.

2.1 Algorithm
Before describing the algorithm, we review some useful notations and concepts, some of which were introduced in [13]. For a row i of A and ℓ = k1/3 , let big(i) := {j : aij > 1/2}, med(i) := {j : 1/ℓ ≤ aij ≤
1/2}, and tiny(i) := {j : 0 < aij < 1/ℓ}, which denote the set of big, medium, and tiny items with respect
to constraint i. For a given randomly sampled set R and an item j ∈ R, we have three kinds of blocking
events for j. Blocking events occur when a set of items cannot all be rounded up without violating some
constraint. In other words, theses events, with probability 1, prevent j from being rounded up. We partition
the blocking events into the following three types:
• BB(j): There exists some constraint i with aij > 0 and an item j ′ 6= j such that j ′ ∈ big(i) ∩ R.
• MB(j): There exists some constraint i with med(i) ∋ j such that | med(i) ∩ R| ≥ 3.
X
• TB(j): There exists some constraint i with tiny(i) ∋ j such that
aij ′ > 1 − aij .
j ′ 6=j:
j ′ ∈(med(i)∪tiny(i))∩R

Informally, we refer to the above three blocking events as big, medium and tiny blocking events for j
with respect to R.
The main algorithm of Bansal et al. [13]. As briefly mentioned in Section 1.1, Bansal et al. add certain
valid constraints on big items to the natural LP relaxation in (3) as follows:
X
max{w · x s.t. A · x ≤ 1and ∀i ∈ [m]
xj ≤ 1, x ∈ [0, 1]n }where A[j] = aj
(7)
j∈big(i)

Algorithm 1, BKNS, gives a formal description of the algorithm of Bansal et al. [13], in which they set
α = 1.
Algorithm 1: BKNS(α)
1

2

3

4

Sampling: Sample each item j independently with probability (αxj )/k and let R0 be the set of
sampled items.
Discarding low-probability events: Remove an item j from R0 if either a medium or tiny blocking
event occurs for j with respect to R0 . Let R1 ⊆ R0 be the set of items not removed.
Deterministic alteration: Remove an item j from R1 if a big blocking event occurs for j with
respect to R1 .
Let RF ⊆ R1 be the set of items not removed; return RF .

Theorem 5 (Bansal et al. [13]). By choosing α = 1, Algorithm 1 yields a randomized ek+o(k)-approximation
for k -CS-PIP.

8

Our algorithm for k -CS-PIP via randomized alterations. Our pre-processing is similar to BKNS with
the crucial difference that α ≫ 1 (but not too large), i.e., we do not attenuate too aggressively; furthermore,
our alteration step is quite different. Let [n] = {1, 2, . . . , n} denote the set of items. We first sample
each item independently using an appropriate product distribution over the items (as mentioned above, we
crucially use a different value for α than BKNS). Let R0 denote the set of sampled items. We remove
items j from R0 for which either a medium or tiny blocking event occurs to obtain a set R1 . We next
perform a randomized alteration, as opposed to a deterministic alteration such as in line 3 of BKNS. We
then randomly and appropriately shrink R1 to obtain the final set RF .
We now informally describe our randomized alteration step. We construct a directed graph G = (R1 , E)
from the constraints as follows. For every item j ∈ R1 , we create a vertex. We create a directed edge from
item j to item j ′ 6= j in G iff j ′ causes a big blocking event for j (i.e., there exists a constraint i where j has
a non-zero coefficient and j ′ is in big(i)). We claim that the expected degree of every vertex in this graph
constructed with R1 is at most α = ω(1). If any vertex j has a degree greater than d := α + α2/3 , we will
remove j from R1 . Hence we now have a directed graph with every vertex having a degree of at most d. We
claim that we can color the undirected version of this directed graph with at most 2d + 1 colors. We choose
one of the colors c in [2d + 1] uniformly at random and add all vertices of color c into RF . Algorithm 2
gives a formal description of our approach.
Algorithm 2: The Algorithm for k -CS-PIP
1

2
3

Sampling: Sample each item j independently with probability αxj /k (where, say, α = log k) and
let R0 be the set of sampled items.
Discarding low-probability events: Remove an item j from R0 if either a medium or tiny
blocking event occurs for j with respect to R0 . Let R1 be the set of items not removed.
Randomized alteration:
(a) Create a directed graph: For every item in R1 , create a vertex in graph G. Add a directed
edge from item j to item j ′ if there exists a constraint i such that aij > 0 and aij ′ ≥ 1/2.
(b) Removing anomalous vertices: For every vertex v in G, if the out-degree of v is greater
than d := α + α2/3 , call v anomalous. Remove all anomalous vertices from G to obtain G′
and let the items corresponding to the remaining vertices in G′ be R2 .
(c) Coloring G′ : Assign a coloring χ to the vertices of G′ using 2d + 1 colors as described in
the text such that for any edge e (ignoring the direction), both end points of e receive
different colors.

4

(d) Choosing an independent set: Choose a number c ∈ [2d + 1] uniformly at random. Add all
vertices v from G′ into RF such that χ(v) = c.
Return RF .

Example. Before moving to the analysis, we will show an example of how the randomized alteration
(i.e., lines 3(a-d) of Algorithm 2) works. We will illustrate this on the integrality gap example considered in
[13]. In this example, we have n = 2k − 1 items and m = 2k − 1 constraints. The weights of all items are
1. For some 0 < ǫ ≪ 1/(nk), the matrix A is defined as follows. ∀i, j ∈ [2k − 1] we have,


if i = j
1
aij := ǫ
if j ∈ {i + 1, i + 2, . . . , i + k − 1(modn)}


0
otherwise
9

As noted in [13], setting xj = (1 − kǫ) for all j ∈ [n] is a feasible LP solution, while the optimal
integral solution has value 1. After running line 1 of the algorithm, each item j is selected with probability
(1 − o(1))α/k independently. For simplicity, we will assume that there are no medium or tiny blocking
events for every j (these only contribute to the lower-order terms). Note that in expectation the total number
of chosen items will be approximately 2α; with high probability, the total number of vertices in the graph
will be n1 := 2α+o(α). Let b1 , b2 , . . . , bn1 denote the set of items in this graph. The directed graph contains
the edge (bi , bj ) for all distinct i, j; for simplicity, assume that the graph has no anomalous vertices. Since
the undirected counterpart of this graph is a complete graph, every vertex will be assigned a unique color;
thus the solution output will have exactly one vertex with probability 1 − o(1).

2.2 Analysis
We prove the following main theorem using Algorithm 2 with α = log(k).
Theorem 1. There exists a randomized rounding algorithm for k -CS-PIP with approximation ratio at most
2k + o(k) for linear objectives.
We will divide the analysis into three parts. At a high-level the three parts prove the following.
• Part 1 (Proved in Lemma 1). For directed graphs with maximum out-degree at most d, there exists a
coloring χ and a corresponding algorithm such that the number of colors used, |χ|, is at most 2d + 1.
• Part 2 (Proved in Lemma 2). For any item j ∈ R1 , the event that the corresponding vertex in G
has an out-degree larger than d occurs with probability at most o(1). This implies that conditional on
j ∈ R1 , the probability that j is present in G′ is 1 − o(1).
• Part 3 (Proved in Lemma 3). For each item j ∈ R0 , either a medium or a tiny blocking event occurs
with probability at most o(1) (again, for our choice α = log(k)). This implies that for each j ∈ R0 ,
it will be added to R1 with probability 1 − o(1).
We assume the following lemmas which are proven in Section 7.1.
Lemma 1. Given a directed graph G = (V, E) with maximum out-degree at most d, there is a polynomialtime algorithm that finds a coloring χ of G’s undirected version such that |χ|, the number of colors used by
χ, is at most 2d + 1.
Lemma 2. For any item j, the probability – conditional on the event “j ∈ R1 ” – that j is selected into R2
(i.e., j ∈ R2 ) is 1 − o(1), for α = log(k).
Lemma 3. For each item j, either a medium or a tiny blocking event occurs with probability – conditional
on the event “j ∈ R0 ” – of at most Θ(α4/3 /k1/3 ) = o(1), for α = log k.
We can now prove the main theorem, Theorem 1.
Proof. First we show that RF is feasible for our original IP. We have the following observations about
Algorithm 2: (i) from line 2, “Discarding low-probability events”, we have that no item in RF can be
blocked by either medium or tiny blocking events; (ii) from the “Randomized alteration” steps in line 3, we
have that no item in RF has any neighbor in G′ that is also included in RF . This implies that no item in
RF can be blocked by any big blocking events. Putting together the two observations implies that RF is a
feasible solution to our IP.
10

We now show that the probability of j being in RF can be calculated as follows.
Pr[j ∈ RF ] = Pr[j ∈ R0 ] · Pr[j ∈ R1 | j ∈ R0 ] · Pr[j ∈ R2 | j ∈ R1 ] · Pr[j ∈ RF | j ∈ R2 ]
1
αxj
· (1 − o(1)) · (1 − o(1)) ·
≥
k
2α + 2α2/3 + 1
xj
=
2k(1 + o(1))
The first inequality is due to the following. From the sampling step we have that Pr[j ∈ R0 ] = αxj /k.
From Lemma 3 we have that Pr[j ∈ R1 | j ∈ R0 ] = 1 − o(1). Lemma 2 implies that Pr[j ∈ R2 | j ∈ R1 ] =
1 − o(1). Finally from Lemma 1 we have that the total number of colors needed for items in R2 is at most
2d + 1, and hence the probability of picking j’s color class is 1/(2d + 1). Thus, Pr[j ∈ RF | j ∈ R2 ] =
1/(2α + 2α2/3 + 1) (recall that d := α + α2/3 ).
Nearly-negative correlation. The natural approach to proving Lemma 1 can introduce substantial positive
correlation among the items included in RF . However, by slightly modifying the algorithm, we can obtain
the following Theorem, which induces nearly-negative correlation in the upper direction among the items.
Theorem 6. Given any constant ǫ ∈ (0, 1), there is an efficient randomized algorithm for rounding a
fractional solution within the k -CS-PIP polytope, such that
1. For all items j ∈ [n], Pr[j ∈ RF ] ≥

xj
2k(1+o(1)) .

2. For any t ∈ [n] and any t-sized subset {v1 , v2 , . . . , vt } of items in [n], we have (with d = α + α2/3 ∼
log k as above)
Pr[v1 ∈ RF ∧ v2 ∈ RF ∧ . . . ∧ vt ∈ RF ] ≤ (2dǫ )t−1 ·

t
Y
xvj
.
2k

j=1

2.3 Extension to Submodular Objectives
As described in the preliminaries, we can extend certain contention-resolution schemes to submodular objectives using prior work. We will now show that the above rounding scheme can be extended to submodular
objectives; in particular, we will use the following definition and theorem from Chekuri et al. [32] 11 .
Definition 1. (bc-BALANCED MONOTONE CR SCHEMES [32]) Let b, c ∈ [0, 1] and let N := [n] be
a set of items. A bc-balanced CR scheme π for PI (where PI denotes the convex relaxation of the set of
feasible integral solutions I ⊆ 2N ) is a procedure which for every y ∈ bPI and A ⊆ N , returns a set
πy (A) ⊆ A ∩ support(y) with the following properties:
(a) For all A ⊆ N, y ∈ bPI , we have that πy ∈ I with probability 1.
(b) For all i ∈ support(y), y ∈ bPI , we have that Pr[i ∈ πy (R(y)) | i ∈ R(y)] ≥ c, where R(y) is
the random set obtained by including every item i ∈ N independently with probability yi .
(c) Whenever i ∈ A1 ⊆ A2 , we have that Pr[i ∈ πy (A1 )] ≥ Pr[i ∈ πy (A2 )].
11

Specifically, Definition 1.2 and Theorem 1.5 from [32].

11

Theorem 7 (Chekuri et al. [32]). Suppose PI admits a bc-balanced monotone CR scheme and ηf is the
approximation ratio for max{F (x) : x ∈ PI ∩ {0, 1}n } (here, F (x) is the multi-linear extension of the
sub-modular function f ). Then there exists a randomized algorithm which gives an expected 1/(bcηf )approximation to maxS∈I f (S), when f is a non-negative submodular function.
For the case of monotone sub-modular functions, we have the optimal result ηf = 1−1/e (Vondrák [68]).
For non-monotone sub-modular functions, the best-known algorithms have ηf ≥ 0.372 due to Ene and
Nguyen [36] and more recently ηf ≥ 0.385 due to Buchbinder and Feldman [20] (it is not known if these
are tight: the best-known upper bound is ηf ≤ 0.478 due to Oveis Gharan and Vondrák [56]).
We will show that Algorithm 2 is a 1/(2k + o(k))-balanced monotone CR scheme, for some b, c such
that bc = 1/(2k + o(k)). Hence, from Theorem 7 we have a (2k + o(k))/ηf -approximation algorithm for
k -CS-PIP with sub-modular objectives. This yields Corollary 1.
For ease of reading, we will first re-state notations used in Definition 1 in the form stated in the previous
sub-section. The polytope PI represents the k -CS-PIP polytope defined by Eq. 7. The vector y is defined
as yi := αxi /k which is used in the Sampling step of the algorithm (i.e., Line 1). The scheme πy is the
procedure defined by lines 1, 2, 3 of the algorithm. In other words, this procedure takes a subset A of items
and returns a feasible solution with probability 1 (and hence satisfying property (a) in the definition). Our
goal then is to show that it further satisfies properties (b) and (c).
The set R(y) corresponds to the set R0 , where every item i is included into R0 with probability yi ,
independently. From the sampling step of the algorithm, we have that b = α/k, since each item i is included
in the set R(y) with probability yi := xi α/k and x ∈ PI and hence y ∈ (α/k)PI . From the alteration
steps we have that c = (1 − o(1))/(2α + o(α)), since for any item i, we have Pr[i ∈ RF | i ∈ R0 ] ≥
(1 − o(1))/(2α + o(α)). Thus, πy satisfies property (b).
Now we will show that the rounding scheme πy satisfies property (c) in Definition 1. Let A1 and A2 be
two arbitrary subsets such that A1 ⊆ A2 . Consider a j ∈ A1 . We will now prove the following.
Pr[j ∈ RF | R0 = A1 ] ≥ Pr[j ∈ RF | R0 = A2 ]
Note that for i ∈ {1, 2} we have,
Pr[j ∈ RF | R0 = Ai ] = Pr[j ∈ RF | j ∈ R2 , R0 = Ai ] Pr[j ∈ R2 | R0 = Ai ]

(8)

For both i = 1 and i = 2, the first term in the RHS of Eq. (8) (i.e., Pr[j ∈ RF | j ∈ R2 , R0 = Ai ]) is same
and is equal to 1/(2d + 1). Note that the second term in the RHS of Eq. (8) (i.e., Pr[j ∈ R2 | R0 = Ai ])
can be rewritten as Pr[j ∈ R2 | j ∈ R0 , Ro = Ai ] since j ∈ A1 and R0 = Ai for i ∈ {1, 2}. From lines 2
and 3(b) of the algorithm we have that the event j ∈ R2 conditioned on j ∈ R0 occurs if and only if:
(i) no medium or tiny blocking events occurred for j.
(ii) vertex j did not correspond to an anomalous vertex in G (one with out-degree greater than d :=
α + α2/3 ).
Both (i) and (ii) are monotonically decreasing in the set R0 (i.e., if it holds for R0 = A2 then it holds for
R0 = A1 ). Hence we have Pr[j ∈ R2 | R0 = A1 ] ≥ Pr[j ∈ R2 | R0 = A2 ].

3 The Stochastic k-Set Packing Problem
Consider the stochastic k-set packing problem defined in the introduction. We start with a second-chancebased algorithm yielding an improved ratio of 8k/5 + o(k). We then improve this to k + o(k) via multiple
12

chances. Recall that if we probe an item j, we have to add it irrevocably, as is standard in such stochasticoptimization problems; thus, we do not get multiple opportunities to examine j. Let x be an optimal solution
to the benchmark LP (4) and C(j) be the set of constraints that j participates in.
Bansal et al. [12] presented Algorithm 3, SKSP(α). They show that SKSP(α) will add each item j
with probability at least β (xj /k) where β ≥ α(1 − α/2). By choosing α = 1, SKSP(α) yields a ratio of
2k.12
Algorithm 3: SKSP(α) [12]
1
2
3

4

Let R denote the set of chosen items which starts out as an empty set.
For each j ∈ [n], generate an independent Bernoulli random variable Yj with mean αxj /k.
Choose a uniformly random permutation π over [n] and follow π to check each item j one-by-one:
add j to R if and only if Yj = 1 and j is safe (i.e., each resource i ∈ C(j) has at least one unit of
budget available); otherwise skip j.
Return R as the set of chosen items.

At a high level, our second-chance-based algorithm proceeds as follows with parameters {α1 , β1 , α2 } to
be chosen later. During the first chance, we set α = α1 and run SKSP(α1 ). Let E1,j denote the event that j
is added to R in this first chance. From the analysis in [12], we have that Pr[E1,j ] ≥ (xj /k) α1 (1 − α1 /2).
By applying simulation-based attenuation techniques, we can ensure that each item j is added to R in the
first chance with probability exactly equal to β1 xj /k for a certain β1 ≤ α1 (1 − α1 /2) of our choice.13
In other words, suppose we obtain an estimate Ê1,j := Pr[E1,j ]. When running the original randomized
algorithm, whenever j can be added to R in the first chance, instead of adding it with probability 1, we add
it with probability ((xj /k) β1 )/Ê1,j .
In the second chance, we set α = α2 and modify SKSP(α2 ) as follows. We generate an independent
Bernoulli random variable Y2,j with mean α2 xj /k for each j; let Y1,j denote the Bernoulli random variable
from the first chance. Proceeding in a uniformly random order π2 , we add j to R if and only if j is safe,
Y1,j = 0 and Y2,j = 1. Algorithm 4, SKSP(α1 , β1 , α2 ), gives a formal description.
Algorithm 4: SKSP(α1 , β1 , α2 )
1
2
3

4

Initialize R as the empty set.
The first chance: Run SKSP(α1 ) with simulation-based attenuation such that Pr[E1,j ] = β1 xj /k
for each j ∈ [n], with β1 ≤ α1 (1 − α1 /2). R now denotes the set of variables chosen in this chance.
The second chance: Generate an independent Bernoulli random variable Y2,j with mean α2 xj /k for
each j. Follow a uniformly random order π2 over [n] to check each item j one-by-one: add j to R if
and only if j is safe, Y1,j = 0, and Y2,j = 1; otherwise, skip it.
Return R as the set of chosen items.

Lemma 4 lower bounds the probability that an item gets added in the second chance. For each j, let E2,j
be the event that j is added to R in the second chance.
12

The terminology used in [12] is actually 1/α; however, we find the inverted notation α more natural for our calculations.
See footnote in Section 1.2. Sampling introduces some small sampling error, but this can be made into a lower-order term with
high probability. We thus assume for simplicity that such simulation-based approaches give us exact results.
13

13

Lemma 4. After running SKSP(α1 , β1 , α2 ) on an optimal solution x to the benchmark LP (4), we have


α x
x
Pr[E2,j ] ≥ kj α2 1 − 1k j − β1 − α22

We can use Lemma 4 to show that we get an approximation ratio of 8k/5. Observe that the events E1,j
and E2,j are mutually exclusive. Let Ej be the event that j has been added to R after the two chances. Then,
5x

x2

by choosing α1 = 1, β1 = 1/2, and α2 = 1/2, we have Pr[Ej ] = Pr[E1,j ]+Pr[E2,j ] = 8kj − 2kj2 . From the
Linearity of Expectation, we get that the total expected weight of the solution is at least (5/8k − o(k))w.x.
Theorem 8. By choosing α1 = 1, β1 = 1/2, and α2 = 1/2, SKSP(α1 , β1 , α2 ) achieves a ratio of
for SKSP.

8k
5 +o(k)

3.1 Extension to T Chances
Intuitively, we can further improve the ratio by performing a third-chance probing and beyond. We present
a natural generalization of (α1 , β1 , α2 ) to ({αt , βt | t ∈ [T ]}) with T chances, where {αt , βt | t ∈ [T ]} are
parameters to be fixed later. Note that (α1 , β1 , α2 ) is the special case wherein T = 2.
During each chance t ≤ T , we generate an independent Bernoulli random variable Yt,j with mean
αt xj /k for each j. Then we follow a uniform random order πt over [n] to check each item j one-by-one:
we add j to R if and only if j is safe, Yt′ ,j = 0 for all t′ < t and Yt,j = 1; otherwise we skip it. Suppose
for a chance t, we have that each j is added to R with probability at least βt xj /k. As before, we can apply
simulation-based attenuation to ensure that each j is added to R in chance t with probability exactly equal
to βt xj /k. Notice that to achieve this goal we need to simulate our algorithm over all previous chances up
to the current one t. Algorithm 5, SKSP({αt , βt |t ∈ [T ]}), gives a formal description of the algorithm.
Notice that during the last chance T , we do not need to perform simulation-based attenuation. For the sake
of clarity in presentation, we still describe it in the algorithm description.
Algorithm 5: SKSP({αt , βt |t ∈ [T ]})
1
2
3

4

5

Initialize R as the empty set.
for t=1, 2, . . . , T do
Generate an independent Bernoulli random variable Yt,j with mean αt xj /k for each j. Follow a
uniform random order πt over [n] to check each item j one-by-one: add j to R if and only if j is
safe, Yt′ ,j = 0 for all t′ < t, and Yt,j = 1; otherwise, skip it.
Apply simulation-based attenuation such that each j is added to R in the tth chance with
probability equal to βt xj /k.
Return R as the set of chosen items.

′ be the event that j is added to R in the tth chance before line 3 of the algorithm
For each item j, let Et,j
for t (i.e., before the start of the tth iteration of the loop). Lemma 5 lower bounds the probabilities of these
events.

Lemma 5. After running ({αt , βt | t ∈ [T ]}) on an optimal solution x to the benchmark LP (4), we have
P
 


P
αt t′ <t αt′
αt
′ ] ≥ xj α 1 −
′
Pr[Et,j
−
β
−
′
t
t <t t
k
2
k
14

Combining Lemma 5 and simulation-based attenuation, we have that for any given {αt′ | t′ ≤ t} and
in chance t with probability equal to βt xj /k for any
{βt′ | t′ < t}, each
 to RP
P item j is added
βt ≤ αt 1 − t′ <t βt′ − αt /2 − αt t′ <t αt′ /k. For each j, let Ej,t be the event that j is added to R
5, we have that the
in chance t and Ej the event that j is added to R after T chances.
From Algorithm
P
P
events {Ej,t | t ≤ T } are mutually exclusive. Thus, Pr[Ej ] = t≤T Pr[Ej,t ] = t≤T βt xj /k. Therefore,
to maximize the final ratio, we will solve the following optimization problem.
max

X

t∈[T ]

βt s.t. βt ≤ αt

1−

X
t′ <t

αt
βt′ −
2

!

−

αt

P

t′ <t αt′

k

∀t ∈ [T ], αt ≥ 0 ∀t ∈ [T ]

(9)

Consider a simplified version of maximization program (9) by ignoring the O(1/k) term as follows.
!
X
X
αt
∀t ∈ [T ], αt ≥ 0 ∀t ∈ [T ]
(10)
max
βt , s.t. βt ≤ αt 1 −
βt′ −
2
′
t <t

t∈[T ]

Lemma 6. An optimal solution to the program (10) is
βt∗ =

X
X
1
(1 −
βt∗′ )2 , ∀t ≥ 1, α∗t = 1 −
βt∗′ , ∀t ≥ 1
2
′
′
t <t

t <t

where β0∗ = 0, 0 ≤ α∗t ≤ 1 for all t ≥ 1 and limT →∞

PT

∗
t=1 βt

= 1.

Theorem 9. Let T P
be some slowly-growing function of k, e.g., T = log k. For each t ∈ [T ], set ᾱt =
α∗t ( t′ <t α∗t′ )
∗
∗
. Then we have (1) {ᾱt , β̄t | t ∈ [T ]} is feasible to the program (9) and (2)
α
k
Pt , β̄t = βt −
t∈[T ] β̄t = 1 + o(1) where o(1) goes to 0 when k goes to infinity. Thus, SKSP({ᾱt , β̄t |t ∈ [T ]}) achieves
a ratio of k + o(k) for SKSP.

4 Hypergraph Matching
In this section, we give a non-uniform attenuation approach to the hypergraph matching problem which leads
to improved competitive ratios. Additionally as stated in the introduction, this takes us “half the remaining
distance” towards resolving the stronger Conjecture 2.
Consider a hypergraph H = (V, E). Assume each e ∈ E has cardinality |e| = ke . Let x = {xe } be an
optimal solution to the LP (5). We start with a warm-up algorithm due to Bansal et al. [12]14 . Algorithm 6,
HM(α), summarizes their approach.
Lemma 7. Each edge e is added to R with probability at least

xe
ke +1

in HM(α) with α = 1.

It can be shown that in HM(α = 1), the worst case occurs for the edges e with xe ≤ ǫ ≈ 0 (henceforth
referred to as “tiny” edges). In contrast, for the edges with xe ≫ ǫ (henceforth referred to as “large” edges),
the ratio is much higher than the worst case bound. This motivates us to balance the ratios among tiny
and large edges. Hence, we modify Algorithm 6 as follows: we generate an independent Bernoulli random
variable Ye with mean g(xe ) for each e, where g : [0, 1] → [0, 1] and g(x)/x is decreasing over [0, 1].
Algorithm 7 gives a formal description of this modified algorithm.
14

Similar to our algorithm for SKSP, we use the notation α while [12] use 1/α.

15

Algorithm 6: HM(α)
1

2
3
4

Initialize R to be the empty set. We will add edges to this set during the algorithm and return it at the
end as the matching.
For each e ∈ E, generate an independent Bernoulli random variable Ye with mean αxe .
Choose a random permutation π over E and follow π to check each edge one-by-one: add e to R if
and only if Ye = 1 and e is safe (i.e., none of the vertices in e are matched); otherwise skip it.
Return R as the matching.

Algorithm 7: HM(g)
1
2
3

4

Initialize R to be the empty set.
For each e ∈ E, generate an independent Bernoulli random variable Ye with mean g(xe ).
Choose a random permutation π over E and follow π to consider each edge one by one: add e to R if
Ye = 1 and e is safe; otherwise skip it.
Return R as the matching

Observe that HM(α) is the special case wherein g(xe ) = αxe . We now consider the task of finding the
optimal g such that the resultant ratio achieved by HM(g) is maximized. Consider a given e with xe = x.
′ 6= e, we say e′ is a neighbor of e (denoted by e′ ∼ e) if e′ ∋ v for some v ∈ e. From the LP (5),
For any eP
we have e′ ∼e xe′ ≤ ke (1 − x). Let Ee be the event that e is added to R. By applying an analysis similar
to the proof of Lemma 7, we get the probability of Ee is at least
R1Q
(11)
Pr[Ee ] ≥ g(x) 0 e′ ∼e (1 − tg(xe′ ))dt.

Therefore our task of finding an optimal g to maximize the r.h.s. of (11) is equivalent to finding maxg F(g),
where F(g) is defined in equation (12).
i
h
.
×
r(x)
(12)
F(g) = minx∈[0,1] g(x)
x
In equation (12), r(x) is defined as

R1Q
P
.
r(x) = min 0 e′ ∼e 1 − tg(xe′ ) dt, where e′ ∼e xe′ ≤ ke (1 − x), xe′ ∈ [0, 1], ∀e′

Lemma 8. By choosing g(x) = x(1 − x2 ), we have that the minimum value of F(g) in Eq. (12) is F(g) =
1
ke (1 − exp(−ke )).
We now prove the main result, Theorem 3.
Proof. Consider HM(g) as shown in Algorithm 7 with g(x) = x(1 − x/2). Let R be the random matching
returned. From Lemma 8, we have that each e will be added to R with probability at least xe F(g) =
xe
ke (1 − exp(−ke )).

16

5 More Applications
In this section, we briefly describe how a simple simulation-based attenuation can lead to improved contention resolution schemes for UFP-TREES with unit demands. This version of the problem was studied
by Chekuri et al. [30] where they gave a 4-approximation for the linear objective case. They also described
a simple randomized algorithm that obtains a 27-approximation15 . Later, Chekuri et al. [32] developed
the machinery of contention resolution schemes, through which they extended it to a 27/ηf -approximation
algorithm for non-negative submodular objective functions (where ηf denotes the approximation ratio for
maximizing non-negative submodular functions16 ). We show that using simple attenuation ideas can further improve this 27/ηf -approximation to an 8.15/ηf -approximation. We achieve this by improving the
1/27-balanced CR scheme17 to a 1/8.15-balanced CR scheme and hence, from Theorem 1.5 of [32], the
approximation ratio follows.
Consider the natural packing P
LP relaxation. Associate a variable xi with every demand pair. Our
constraint set is: for every edge e, i:e∈Pi xi ≤ ue , where ue is the capacity of e. Our algorithm (formally
described in Algorithm 8) proceeds similar to the one described in [30], except at line 3, where we use our
attenuation ideas.
Algorithm 8: Improved contention resolution Scheme UFP-TREES with unit demands
1
2
3

4

Root the tree T arbitrarily. Let LCA(si , ti ) denote the least common ancestor of si and ti .
Construct a random set R of demand pairs, by including each pair in R independently with
probability αxi .
Consider the demand pairs in increasing distance of their LCA from the root. Let Rfinal denote the set
of pairs included in the rounded integral solution. For every demand pair i, simulate the run of the
algorithm from beginning (i.e., produce many samples of R and separately run the algorithm on
these samples) to obtain the estimate ηi of the probability of i to be safe (i.e., none of the edges in
the path has exhausted capacities). Suppose i is safe, add it to Rfinal with probability β/ηi .
Return Rfinal as the set of demands chosen from routing.

Analysis. For the most part, the analysis is similar to the exposition in Chekuri et al. [32]. We will highlight
the part where attenuation immediately leads to improved bounds.
Consider a fixed pair (si∗ , ti∗ ) and let ℓ := LCA(si∗ , ti∗ ) in T . Let P and P ′ denote the unique path in
the tree from ℓ to si∗ and ℓ to ti∗ respectively. As in [32], we will upper bound the probability of i∗ being
unsafe due to path P and a symmetric argument holds for P ′ . Let e1 , e2 , . . . , eλ be the edges in P from ℓ
to si∗ . Let Ej denote the event that i∗ is not safe to be added in line 3 of Algorithm 8, because of overflow
at edge ej . Note that for j > h and uej ≥ ueh , event Ej implies Eh and hence Pr[Ej ] ≤ Pr[Eh ]. Note,
this argument does not change due to attenuation since the demands are processed in increasing order of
the depth and any chosen demand pair using edge ej also has to use eh up until the time i∗ is considered.
Thus, we can make a simplifying assumption similar to [32] and consider a strictly decreasing sequence
of capacities ue1 > ue2 > . . . > ueλ ≥ 1. Let Sj denote the set of demand pairs that use edge ej . The
following steps is the part where our analysis differs from [32] due to the introduction of attenuation.
Define, β := 1 − 2αe/(1 − αe) and γ := αβ. Note that without attenuation, we have ηi ≥ β for all i
from the analysis in [32].
15

This can be obtained by maximizing over all 0 < b < 1/3e in Lemma 4.19 of [32], which yields approximately 1/27.
See the section on k -CS-PIP for a discussion on various values of ηf known.
17
See the section on extension to sub-modular objectives in k -CS-PIP for defintion of a balanced CR scheme.

16

17

Let Ej′ denote the event that at least uej demand pairs
Pout of Sj are included in the final solution. Note
′
that Pr[Ej ] ≤ Pr[Ej ]. From the LP constraints we have i∈Sj xi ≤ uej .
LetPXi denote the indicator random variable for the following event: {i ∈ R ∧ i ∈ Rfinal }. We define
X := i∈Sj Xi .
Note that, event Ej′ happens if and only if X ≥ uej and hence we have, Pr[Ej′ ] = Pr[X ≥ uej ].
Additionally, we have that the Xi ’s are “cylindrically negatively correlated” and hence we can apply the
Chernoff-Hoeffding bounds due to Panconesi and Srinivasan [57]. Observe that E[X] ≤ γuej (since each
i is included in R independently with αxi and then included in Rfinal with probability exactly β) and for
1 + δ = 1/γ, we have Pr[X ≥ uej ] ≤ (e/(1 + δ))(1+δ)µ ≤ (γe)uej . Hence, taking a union bound
over all
the edges in the path, we have the probability of i∗ being unsafe due to an edge in P to be at
P∞
most q=1 (γe)ℓ = (γe)/(1 − γe) (We used the fact that ue1 > ue2 > . . . > ueλ ≥ 1). Combining
the symmetric analysis for the other path P ′ , we have the probability of i∗ being unsafe to be at most
2γe/(1 − γe). Note that we used the fact that γe < 1 in the geometric series. Additionally, since γ ≤ 1, we
have that 2γe/(1 − γe) ≤ 2αe/(1 − αe). Hence, using ηi ≥ β is justified.
Now to get the claimed approximation ratio, we solve the following maximization problem:
max {α · (1 − 2γe/(1 − γe)) : β = 1 − 2αe/(1 − αe), γ = α ∗ β, 0 ≤ γe < 1/3}

0≤α≤1

which yields a value of 1/8.15.

6 Conclusion and Open Problems
In this work, we described two unifying ideas, namely non-uniform attenuation and multiple-chance probing to get bounds matching integrality gap (up to lower-order terms) for the k -CS-PIP and its stochastic
counterpart SKSP. We generalized the conjecture due to Füredi et al. [39] (FKS conjecture) and went
“halfway” toward resolving this generalized form using our ideas. Finally, we showed that we can improve
the contention resolution schemes for UFP-TREES with unit demands. Our algorithms for k -CS-PIP
can be extended to non-negative submodular objectives via the machinery developed in Chekuri et al. [32]
and the improved contention resolution scheme for UFP-TREES with unit demands leads to improved
approximation ratio for submodular objectives via the same machinery.
This work leaves a few open directions. The first concrete problem is to completely resolve the FKS
conjecture and its generalization. We believe non-uniform attenuation and multiple-chances combined with
the primal-dual techniques from [39] could give the machinery needed to achieve this. Other open directions are less well-formed. One is to obtain stronger LP relaxations for the k -CS-PIP and its stochastic
counterpart SKSP such that the integrality gap is reduced. The other is to consider improvements to related
packing programs, such as column-restricted packing programs or general packing programs.

7 Proofs
7.1 Proofs for Section 2 (k -CS-PIP)
We will now provide the missing proofs for k -CS-PIP.
Proof of Lemma 1. We will prove this Lemma by giving a coloring algorithm that uses at most 2d + 1
colors and prove its correctness. Recall that we have a directed graph such that the maximum out-degree
∆ ≤ d. The algorithm is a simple greedy algorithm, which first picks the vertex with minimum total
18

degree (i.e., sum of in-degree plus out-degree). It then removes this vertex from the graph and recursively
colors the sub-problem. Finally, it assigns a color to this picked vertex not assigned to any of its neighbors.
Algorithm 9 describes the algorithm formally.
Algorithm 9: Greedy algorithm to color bounded degree directed graph
Color-Directed-Graph(G, V, d, χ)
1 if V = φ then
2
return χ
3
4
5
6

7

else
Let vmin denote the vertex with minimum total degree.
χ = Color-Directed-Graph(G, V \ {vmin }, d, χ).
Pick the smallest color c ∈ [2d + 1] that is not used to color any of the neighbors of vmin . Let
χ(vmin ) = c.
return χ

We will now prove the correctness of the above algorithm. In particular, we need to show that in every
recursive call of the function, there is always a color c ∈ [2d + 1] such that the assignment in line 6 of the
algorithm is feasible. We prove this via induction on number of vertices in the graph G.
Base Case: The base case is the first iteration is when the number of vertices is 1. In this case, the statement
is trivially true since vmin has no neighbors.
Inductive Case: We have that ∆ ≤ d for every recursive call. Hence, the sum of total degree of all vertices
in the graph is 2nd (Each edge contributes 2 towards the total degree and there are nd edges). Hence, the
average total degree is 2d. This implies that the minimum total degree in the graph is at most 2d. Hence,
the vertex vmin has a total degree of at most 2d. From inductive hypothesis we have that V \ {vmin } can be
colored with at most 2d + 1 colors. Hence, there exists a color c ∈ [2d + 1], such that χ(vmin ) = c is a valid
coloring (since vmin has at most 2d neighbors).
Proof of Lemma 2. Consider an item j ∈ R1 . We want to show that the Pr[δj > α + α2/3 ] ≤ o(1),
where δj represents the out-degree of j in the directed graph G. Recall that from the construction of graph
G, we have a directed edge from item j to item j ′ if and only there is a constraint i where aij ′ > 1/2 and
aij > 0. For sake of simplicity, let {1, 2, . . . , Nj } denote the set of out-neighbors of j in graph G and
let {X1 , X2 , . . . , XNj } denote the corresponding indicator random variable for them being included in R1 .
Hence, for evey i ∈ [Nj ] we have E[Xi ] = α(1 − o(1))xi /k. From the strengthened constraints in LP (7)
we have that E[δj ] = E[X1 + X2 + . . . + XNj ] ≤ α(1 − o(1)). Hence we have
1/3 )

Pr[δj > α + α2/3 ] ≤ Pr[δj > E[δj ] + α2/3 ] ≤ e−Ω(α

= o(1)

The last inequality is from the Chernoff bounds, while the last equality is true for α = log(k).
Proof of Lemma 3. Consider the medium blocking event MB(j). Let i be a constraint that causes MB(j)
and let j1 , j2 6= j be the two other variables such that j1 , j2 ∈ med(i). Denote, Xj , Xj1 and Xj2 to be the
indicators that j ∈ R0 , j1 ∈ R0 , j2 ∈ R0 respectively.
We know that aij xj + aij1 xj1 + aij2 xj2 ≤ 1 and since j, j1 , j2 ∈ med(i), we have xj + xj1 + xj2 ≤ ℓ
for some constant value of ℓ. The probability that scenario MB is “bad” is if Xj + Xj1 + Xj2 ≥ 2. Note
that E[Xj + Xj1 + Xj2 ] ≤ αℓ
k .
19

Hence, using the the Chernoff bounds in the form denoted in Theorem 10 of Appendix, we have
 2 2
α ℓ
Pr[Xj1 + Xj2 ≥ 2 Xj1 = 1] = Pr[Xj1 + Xj2 ≥ 2] ≤ O
k2
Note that the first equality is due to the fact that these variables are independent. Using a union bound
2 2
over the k constraints j appears in, the total probability of the “bad” event is at most O( α kℓ ). And since
α = O(log k) and ℓ = Θ((k/α)1/3 ), this value is o(1).
For scenario TB(j) we will do the following. If j is tiny, ourP“bad” event for constraint i is that the total
size of remaining items to be at least 1 − 1/ℓ. We know that E[ h∈R\{j} Aih Xih ] ≤ α/k. We want,
P
ℓ
Pr[ h∈R\{j} Aih Xih > 1 − 1/ℓ] ≤ αk . ℓ−1

Note that the inequality follows from Markov’s inequality. Since ℓ ≥ 2, we have that
α
α ℓ
.
≤ .(1 + 2/ℓ)
k ℓ−1
k
Note that taking a union bound over the k constraints, setting ℓ = Θ((k/α)1/3 ) and α = log(k), we
have that αk .(1 + 2/ℓ) = o(1).
Proof of Theorem 6. To prove this theorem, we will now describe a modified version of Algorithm 9. The
other steps in the proof remain the same and will directly imply the theorem. To this end, we will now
describe the modified algorithm and its analysis.
Algorithm 10: Greedy algorithm to color bounded out-degree directed graphs using 2d + d1−ǫ colors,
and with near-negative correlation
Color-Dir-Graph-Neg-Corr(G, V, d, ǫ, χ)
1 if V = φ then
2
return χ
3
4
5
6

7

else
Let vmin denote the vertex with minimum total degree.
χ = Color-Dir-Graph-Neg-Corr(G, V \ {vmin }, d, ǫ, χ).
Among the smallest d1−ǫ colors in [2d + d1−ǫ ] that have not been used thus far to color any of the
neighbors of vmin , choose a color cr uniformly at random. Let χ(vmin ) = cr .
return χ

As before, we will choose one of the colors c in [2d + d1−ǫ ] uniformly at random and include all
vertices which received a color c in the set RF . Since α1−ǫ ≤ o(α), a similar analysis as before follows
to give part (1) of Theorem 6. We will now prove part (2). Fix an arbitrary t ∈ [n] and any t-sized subset
U := {v1 , v2 , . . . , vt } of items in [n]. A necessary condition for these items to be present in G′ is that they
were all chosen into R0 , which happens with probability
Qt xvj α
(13)
j=1 k ;
suppose that this indeed happens (all the remaining probability calculations are conditional on this). Note
that Algorithm 10 first removes the vertex vmin and then recurses; i.e., it removes the vertices one-by-one,
20

starting with vmin . Let σ be the reverse of this order, and suppose that the order of vertices in U according
to σ is, without loss of generality, {v1 , v2 , . . . , vt }. Recall again that our probability calculations now are
conditional on all items in U being present in G′ ; denote such conditional probabilities by Pr′ . Note that
1
. Next, a moment’s reflection shows that for any j with 2 ≤ j ≤ t,
Pr′ [v1 ∈ RF ] = 2d+d1 1−ǫ ≤ 2α
Pr ′ [vj ∈ RF | v1 ∈ RF , v2 ∈ RF , . . . , vj−1 ∈ RF ] ≤

1
d1−ǫ

≤

2dǫ
.
2α

Chaining these together and combining with (13) completes the proof.

7.2 Proofs for Section 3 (SKSP)
We will now provide the missing proofs for SKSP.
Proof of Lemma 4. Let us fix j. Note that “Y1,j = 0 and Y2,j = 1” occurs with probability (1 −
α1 xj /k) (α2 xj /k). Consider a given i ∈ C(j) and let U2,i be the budget usage of resource i when the
algorithm reaches j in the random permutation of the second chance.
Pr[E2,j ] = Pr[Y1,j = 0 ∧ Y2,j = 1] Pr[E2,j | Y1,j = 0 ∧ Y2,j = 1]
#
"

^
α1 xj  α2 xj
= 1−
(U2,i ≤ bi − 1) | Y1,j = 0 ∧ Y2,j = 1
Pr
k
k
i
!

X
α1 xj  α2 xj
1−
Pr [U2,i ≥ bi | Y1,j = 0]
≥ 1−
k
k
i
!
X
α2 xj
α1 xj
≥
1−
−
Pr [U2,i ≥ bi ]
k
k

(14)
(15)

(16)

(17)

i

Let X1,ℓ be the indicator random variable showing if ℓ is added to R in the first chance and 1{2,ℓ} indicate
if item ℓ falls before j in the random order π2 . Thus we have
U2,i ≤
which implies
E[U2,i ] ≤

X
ℓ6=j

ui,ℓ

P



ℓ6=j

SIi,ℓ X1,ℓ + (1 − Y1,ℓ )Y2,ℓ 1{2,ℓ}

β1 xℓ 1 
α1 xℓ  α2 xℓ
1−
+
k
2
k
k



≤





β1 1 α2
+
k
2 k



bi

Plugging the above inequality into (17) and applying Markov’s inequality, we complete the proof of
Lemma 4.
Proof of Theorem 8. Consider a given item j. We have,
Pr[Ej ] = Pr[E1,j ] + Pr[E2,j ]
≥

=

xj
k
xj
k

β1 + α2

α1 xj
k


− β1 − α22


1 − β1 − α22 − O(1/k)

β1 + α2 1 −

To obtain the worst case, we solve the following optimization problem for an (hypothetical) adversary:

21


α2 
max β1 + α2 1 − β1 −
, s.t. 0 ≤ β1 ≤ α1 (1 − α1 /2), α1 ≥ 0, α2 ≥ 0
(18)
2
Solving the above program, the optimal solution is α1 = 1, β1 = 1/2 and α2 = 1/2 with a ratio of
( 58 + o(1))k.
Bernoulli random
variable Zt,j = 1 iff Yt′ ,j = 0 for all
Proof of Lemma 5. Consider an item j and define
α x Q
α x 
t′ < t and Yt,j = 1. Observe that E[Zt,j ] = tk j t′ <t 1 − tk′ j . Consider a given i ∈ C(j) and let Ut,j
be the budget usage of resource i when the algorithm reaches j in the random permutation during chance t.
Thus we have,
′ ] = Pr[Z
′
Pr[Et,j
t,j = 1] Pr[Ej,t | Zt,j = 1]
α x 
α x Q
= tk j t′ <t 1 − tk′ j
V
Pr [ i (Ut,i ≤ bi − 1) | Zt,j = 1]
α x 
α x Q
≥ tk j t′ <t 1 − tk′ j


P
V
1 − i Pr Ut,i ≥ bi | t′ <t Yt′ ,j = 0

P
α x Q
αt′ xj 
≥ tk j
− i Pr [Ut,i ≥ bi ]
t′ <t 1 − k

Notice that
E[Ut,j ] ≤

X
ℓ6=j

P

1 αt
1 Y
αt′ xℓ  αt xℓ
xℓ X
t′ <t βt′
)≤
+
βt′ +
1−
bi
ui,ℓ (
k ′
2 ′
k
k
k
2 k
t <t

t <t

By applying Markov’s inequality, we get
Q
xj
′ ] ≥
Pr[Et,j
t′ <t 1 −
k αt
≥

xj
k



αt (1−

P

t′ <t

β t′ −

αt′ xj 
k

αt
2

)−

αt

−

P

P

t′ <t βt′


+

t′ <t αt′
k

αt
2




P
Proof of Lemma 6. For any given P
{βt | 1 ≤ t < T }, we have βTP≤ αT 1 − t′ <T βt′ − αT /2 . Thus,
the optimal solution is βT∗ = 12 (1 − 1≤t′ <T βt∗′ )2 and αT = 1 − 1≤t′ <T βt∗′ . Thus,

2 
P
P
P
∗ = 1 1+
β
+
β
β
=
β
t
t
t
t<T
T
t∈[T ]
t<T
2
P
P
Therefore the maximization of t≤T βt is reduced to that
P of ∗t≤T −1 βt . By repeating the above analysis
∗
∗
∗
for T times, we get our claim for βt and αt . Let γT = t∈[T ] βt . From the above analysis, we see


∗ )2 , ∀t ≥ 2
γ1∗ = 21 , γt∗ = 21 1 + (γt−1

∗ )2 ≥ 0,
∗
= 12 (1−γt−1
Since γ1∗ ≤ 1, we can prove that γt∗ ≤ 1 for all t by induction. Notice that γt∗ −γt−1
which implies that {γt } is a non-decreasing. Since {γt } is non-decreasing and bounded, it has a limit ℓ. The
only solution to the equation ℓ = (1 + ℓ2 )/2 is ℓ = 1, and hence limT →∞ γT∗ = 1.

Proof of Theorem 9. Observe that for each t ∈ [T ], β̄t ≤ βt∗ . Also,
2 α∗ (P ′ α∗ )
P
β̄t = 12 1 − t′ <t βt∗′ − t tk<t t′

 α∗ P α∗
P
( ′
)
α∗t
∗
∗
= αt 1 − t′ <t βt′ − 2 − t tk<t t′
≤ ᾱt 1 −

P

t′ <t

β̄t′ −
22

ᾱt
2



−

ᾱt (

P

t′ <t

k

ᾱt′ )

Thus we claim that {ᾱt , β̄t | t ∈ [T ]} is feasible for the program (9). Notice that

P
∗
X
X α∗t
X
T2
log2 k
t′ <t αt′
∗
β̄t =
βt −
≥ γT∗ −
= 1 − (1 − γT∗ +
)
k
k
k
t∈[T ]

t∈[T ]

t∈[T ]

From Lemma 6, we have that (1 − γT∗ ) = o(1) thus proving the theorem.

7.3 Proofs for Section 4 (Hypergraph Matching)
We will now provide the missing proofs for Hypergraph Matching.
Proof for Lemma 7. The proof is very similar to that in [15, 12]. For each e ∈ E, let Ee be the event that e
is added to R in HM(α). Consider an edge e and for each v ∈ e, let Lv be the event that v is available when
checking e (in the order given by π). Let π(e) = t ∈ (0, 1).
R 1 V

Pr[Ee ] = αxe 0 Pr v∈e Lv | π(e) = t dt
R1Q Q
≥ αxe 0 v∈e f :f ∋v (1 − tαxf )dt


R1
e
1 − (1 − α)ke +1
≥ αxe 0 (1 − tα)ke dt = kex+1
Thus choosing α = 1 completes the proof of the lemma.

Proof of Lemma 8. Consider a given xe = x with |e| = ke . Notice that for each given t ∈ (0, 1),
P


Q
′
′
)
=
exp
1
−
tg(x
))
ln(1
−
tg(x
′
′
e
e
e ∼e
e ∼e

Note that g(x) = x(1 − x/2) satisfies the condition of Lemma 9 in the Appendix and hence,
P for each
given t 
∈ (0, 1), the function ln(1 − tg(x)) is convex over x ∈ [0, 1]. Thus to minimize e′ ∼e ln(1 −
P
tg(xe′ )) subject to 0 ≤ xe′ ≤ 1 and e′ xe′ ≤ κ with κ = ke (1 − x), an adversary will choose the
following worst case scenario: create κ/ǫ neighbors for e with each xe′ = ǫ and let ǫ → 0. Thus,
min

Y

e′ ∼e

X


1 − tg(xe′ ) = min exp
ln(1 − tg(xe′ )) = lim (1 − tg(ǫ))κ/ǫ = exp(−tκ)
ǫ→0

e′ ∼e

Therefore for each fixed xe = x, the inner minimization program in (12) has an analytic form of optimal
value as follows:
Z 1Y
Z 1

1 − exp(−κ)
exp(−tκ)dt =
min
1 − tg(xe′ ) dt =
(19)
κ
0 ′
0
e ∼e

Plugging this back into (12), we obtain F(g) = minx∈[0,1] G(x), where




.
1
G(x) = 1 − x2 ke (1−x)
1 − exp(−ke (1 − x))

Note that G′ (x) ≥ 0 over x ∈ [0, 1] and thus, the minimum value of G(x) over x ∈ [0, 1] is G(0) =
1
ke (1 − exp(−ke )).

23

References
[1] A DAMCZYK , M. Non-negative submodular stochastic probing via stochastic contention resolution
schemes. CoRR abs/1508.07771 (2015).
[2] A DAMCZYK , M., G RANDONI , F., AND M UKHERJEE , J. Improved approximation algorithms for
stochastic matching. In Algorithms-ESA 2015. Springer, 2015, pp. 1–12.
[3] A DAMCZYK , M., S VIRIDENKO , M., AND WARD , J. Submodular stochastic probing on matroids. In
31st International Symposium on Theoretical Aspects of Computer Science, vol. 25 of LIPIcs. Leibniz
Int. Proc. Inform. 2014, pp. 29–40.
[4] A JTAI , M., KOML ÓS , J.,
29, 3 (1980), 354–360.

AND

S ZEMER ÉDI , E. A note on Ramsey numbers. J. Comb. Theory, Ser. A

[5] A RKIN , E. M., AND H ASSIN , R. On local search for weighted k-set packing. Math. Oper. Res. 23, 3
(1998), 640–648.
[6] A ZAR , Y., AND R EGEV, O. Combinatorial algorithms for the unsplittable flow problem. Algorithmica
44, 1 (2006), 49–66.
[7] BANSAL , N. Constructive algorithms for discrepancy minimization. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010. IEEE Computer Soc., Los Alamitos, CA,
2010, pp. 3–10.
[8] BANSAL , N., C HAKRABARTI , A., E PSTEIN , A., AND S CHIEBER , B. A quasi-PTAS for unsplittable
flow on line graphs. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of
Computing. ACM, New York, 2006, pp. 721–729.
[9] BANSAL , N., DADUSH , D., AND G ARG , S. An algorithm for komlós conjecture matching banaszczyk’s bound. In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
(2016), IEEE, pp. 788–799.
[10] BANSAL , N., F RIGGSTAD , Z., K HANDEKAR , R., AND S ALAVATIPOUR , M. R. A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Algorithms 10, 1 (2014), Art. 1, 15.
[11] BANSAL , N., AND G ARG , S. Improved algorithmic bounds for discrepancy of sparse set systems.
arXiv preprint arXiv:1601.03311 (2016).
[12] BANSAL , N., G UPTA , A., L I , J., M ESTRE , J., NAGARAJAN , V., AND RUDRA , A. When LP is the
cure for your matching woes: improved bounds for stochastic matchings. Algorithmica 63, 4 (2012),
733–762.
[13] BANSAL , N., KORULA , N., NAGARAJAN , V., AND S RINIVASAN , A. Solving packing integer programs via randomized rounding with alterations. Theory Comput. 8 (2012), 533–565.
[14] BANSAL , N.,
451–471.

AND

S PENCER , J. Deterministic discrepancy minimization. Algorithmica 67, 4 (2013),

24

[15] BAVEJA , A., C HAVAN , A., N IKIFOROV, A., S RINIVASAN , A., AND X U , P. Improved bounds in
stochastic matching and optimization. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, vol. 40 of LIPIcs. Leibniz Int. Proc. Inform. 2015, pp. 124–134.
[16] BAVEJA , A., AND S RINIVASAN , A. Approximation algorithms for disjoint paths and related routing
and packing problems. Math. Oper. Res. 25, 2 (2000), 255–280.
[17] B ECK , J.,

AND

F IALA , T. “Integer-making” theorems. Discrete Appl. Math. 3, 1 (1981), 1–8.

[18] B ERMAN , P. A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic
J. Comput. 7, 3 (2000), 178–184.
[19] B RUBACH , B., S ANKARARAMAN , K. A., S RINIVASAN , A., AND X U , P. Attenuate locally, win
globally: An attenuation-based framework for online stochastic matching with timeouts. In Sixteenth
International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017). 2017.
[20] B UCHBINDER , N., AND F ELDMAN , M. Constrained submodular maximization via a non-symmetric
technique. arXiv preprint arXiv:1611.03253 (2016).
[21] B UCHBINDER , N., F ELDMAN , M., NAOR , J., AND S CHWARTZ , R. Submodular maximization with
cardinality constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete
Algorithms (2014), ACM, New York, pp. 1433–1452.
[22] C ALINESCU , G., C HEKURI , C., P ÁL , M., AND VONDR ÁK , J. Maximizing a monotone submodular
function subject to a matroid constraint. SIAM J. Comput. 40, 6 (2011), 1740–1766.
[23] C HAKRABARTI , A., C HEKURI , C., G UPTA , A., AND K UMAR , A. Approximation algorithms for the
unsplittable flow problem. Algorithmica 47, 1 (2007), 53–78.
[24] C HAN , Y. H., AND L AU , L. C. On linear and semidefinite programming relaxations for hypergraph
matching. Math. Program. 135, 1-2, Ser. A (2012), 123–148.
[25] C HANDRA , B., AND H ALLD ÓRSSON , M. M. Greedy local improvement and weighted set packing
approximation. J. Algorithms 39, 2 (2001), 223–240.
[26] C HEKURI , C., E NE , A.,

AND

KORULA , N. Personal communication. 537–538.

[27] C HEKURI , C., E NE , A., AND KORULA , N. Unsplittable flow in paths and trees and columnrestricted packing integer programs. In Approximation, randomization, and combinatorial optimization, vol. 5687 of Lecture Notes in Comput. Sci. Springer, Berlin, 2009, pp. 42–55.
[28] C HEKURI , C., JAYRAM , T. S., AND VONDR ÁK , J. On multiplicative weight updates for concave and
submodular function maximization. In ITCS’15—Proceedings of the 6th Innovations in Theoretical
Computer Science. ACM, New York, 2015, pp. 201–210.
√
[29] C HEKURI , C., K HANNA , S., AND S HEPHERD , F. B. An O( n) approximation and integrality gap
for disjoint paths and unsplittable flow. Theory Comput. 2 (2006), 137–146.
[30] C HEKURI , C., M YDLARZ , M., AND S HEPHERD , F. B. Multicommodity demand flow in a tree and
packing integer programs. ACM Trans. Algorithms 3, 3 (2007), Art. 27, 23.

25

[31] C HEKURI , C., VONDR ÁK , J., AND Z ENKLUSEN , R. Dependent randomized rounding via exchange
properties of combinatorial structures. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010. IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 575–584.
[32] C HEKURI , C., VONDR ÁK , J., AND Z ENKLUSEN , R. Submodular function maximization via the
multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43, 6 (2014), 1831–1879.
[33] D EAN , B. C., G OEMANS , M. X., AND VONDR ÁK , J. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete
Algorithms (2005), ACM, New York, pp. 395–404.
[34] D EAN , B. C., G OEMANS , M. X., AND VONDR ÁK , J. Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33, 4 (2008), 945–964.
[35] E LBASSIONI , K., G ARG , N., G UPTA , D., K UMAR , A., NARULA , V., AND PAL , A. Approximation
algorithms for the unsplittable flow problem on paths and trees. In 32nd International Conference on
Foundations of Software Technology and Theoretical Computer Science, vol. 18 of LIPIcs. Leibniz Int.
Proc. Inform. 2012, pp. 267–275.
[36] E NE , A., AND N GUYEN , H. L. Constrained submodular maximization: Beyond 1/e. In Foundations
of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on (2016), IEEE, pp. 248–257.
[37] F ELDMAN , M., NAOR , J., AND S CHWARTZ , R. A unified continuous greedy algorithm for submodular maximization. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—
FOCS 2011. IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 570–579.
[38] F ISHER , M. L., N EMHAUSER , G. L., AND W OLSEY, L. A. An analysis of approximations for
maximizing submodular set functions. II. Math. Programming Stud., 8 (1978), 73–87. Polyhedral
combinatorics.
[39] F ÜREDI , Z., K AHN , J., AND S EYMOUR , P. D. On the fractional matching polytope of a hypergraph.
Combinatorica 13, 2 (1993), 167–180.
[40] G ARG , N., VAZIRANI , V. V., AND YANNAKAKIS , M. Primal-dual approximation algorithms for
integral flow and multicut in trees. Algorithmica 18, 1 (1997), 3–20.
[41] G UPTA , A., NAGARAJAN , V., AND S INGLA , S. Adaptivity gaps for stochastic probing: Submodular
and XOS functions. CoRR abs/1608.00673 (2016).
[42] G UPTA , A., NAGARAJAN , V., AND S INGLA , S. Algorithms and adaptivity gaps for stochastic probing. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms
(Philadelphia, PA, USA, 2016), SODA ’16, Society for Industrial and Applied Mathematics, pp. 1731–
1747.
[43] H ARVEY, N. J. A., S CHWARTZ , R., AND S INGH , M. Discrepancy without partial colorings. In
Approximation, randomization, and combinatorial optimization, vol. 28 of LIPIcs. Leibniz Int. Proc.
Inform. 2014, pp. 258–273.
[44] H AZAN , E., S AFRA , S., AND S CHWARTZ , O. On the complexity of approximating k-set packing.
Computational Complexity 15, 1 (2006), 20–39.
26

[45] H URKENS , C. A. J., AND S CHRIJVER , A. 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 J. Discrete
Math. 2, 1 (1989), 68–72.
[46] K LEINBERG , J. M. Approximation algorithms for disjoint paths problems. PhD thesis, Citeseer, 1996.
[47] KOLLIOPOULOS , S. G., AND S TEIN , C. Approximating disjoint-path problems using packing integer
programs. Math. Program. 99, 1, Ser. A (2004), 63–87.
[48] KOLMAN , P. A note on the greedy algorithm for the unsplittable flow problem. Inform. Process. Lett.
88, 3 (2003), 101–105.
[49] KOLMAN , P., AND S CHEIDELER , C. Improved bounds for the unsplittable flow problem. J. Algorithms 61, 1 (2006), 20–44.
[50] K ULIK , A., S HACHNAI , H., AND TAMIR , T. Maximizing submodular set functions subject to multiple linear constraints. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete
Algorithms (2009), SIAM, Philadelphia, PA, pp. 545–554.
[51] L EE , J., M IRROKNI , V. S., NAGARAJAN , V., AND S VIRIDENKO , M. Maximizing nonmonotone
submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23, 4 (2009/10),
2053–2078.
[52] L EIGHTON , T., L U , C.-J., R AO , S., AND S RINIVASAN , A. New algorithmic aspects of the local
lemma with applications to routing and partitioning. SIAM J. Comput. 31, 2 (2001), 626–641.
[53] L EVY, A., R AMADAS , H., AND ROTHVOSS , T. Deterministic discrepancy minimization via the
multiplicative weight update method. arXiv preprint arXiv:1611.08752 (2016).
[54] L I , J., AND Y UAN , W. Stochastic combinatorial optimization via Poisson approximation. In Proceedings of the 2013 ACM Symposium on Theory of Computing—STOC’13. ACM, New York, 2013,
pp. 971–980.
[55] L OVETT, S., AND M EKA , R. Constructive discrepancy minimization by walking on the edges. SIAM
J. Comput. 44, 5 (2015), 1573–1582.
[56] OVEIS G HARAN , S., AND VONDR ÁK , J. Submodular maximization by simulated annealing. In
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011),
SIAM, Philadelphia, PA, pp. 1098–1116.
[57] PANCONESI , A., AND S RINIVASAN , A. Randomized distributed edge coloring via an extension of
the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 2 (1997), 350–368.
[58] PAREKH , O. Iterative packing for demand and hypergraph matching. In Integer programming and
combinatorial optimization, vol. 6655 of Lecture Notes in Comput. Sci. Springer, Heidelberg, 2011,
pp. 349–361.
[59] PAREKH , O., AND P RITCHARD , D. Generalized hypergraph matching via iterated packing and local
ratio. In Approximation and online algorithms, vol. 8952 of Lecture Notes in Comput. Sci. Springer,
Cham, 2015, pp. 207–223.

27

[60] P ERES , Y., S INGH , M., AND V ISHNOI , N. Random walks in polytopes and negative dependence. In
Proceedings of the Eighth Annual Innovations in Theoretical Computer Science (Berkeley, CA, 2017)
(2017).
[61] P RITCHARD , D. Approximability of sparse integer programs. In Algorithms—ESA 2009, vol. 5757 of
Lecture Notes in Comput. Sci. Springer, Berlin, 2009, pp. 83–94.
[62] P RITCHARD , D., AND C HAKRABARTY, D. Approximability of sparse integer programs. Algorithmica
61, 1 (2011), 75–93.
[63] R ÖDL , V. On a packing and covering problem. Eur. J. Comb. 6, 1 (1985), 69–78.
[64] ROTHVOSS , T. Constructive Discrepancy Minimization for Convex Sets. SIAM J. Comput. 46, 1
(2017), 224–234.
[65] S RINIVASAN , A. Improved approximations for edge-disjoint paths, unsplittable flow, and related
routing problems. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium
on (1997), IEEE, pp. 416–425.
[66] S RINIVASAN , A. Improving the discrepancy bound for sparse matrices: better approximations for
sparse lattice approximation problems. In Proceedings of the Eighth Annual ACM-SIAM Symposium
on Discrete Algorithms (1997), ACM, New York, pp. 692–701.
[67] S RINIVASAN , A. Improved approximation guarantees for packing and covering integer programs.
SIAM J. Comput. 29, 2 (1999), 648–670.
[68] VONDR ÁK , J. Optimal approximation for the submodular welfare problem in the value oracle model.
In STOC’08. ACM, New York, 2008, pp. 67–74.
[69] WARD , J. A (k + 3)/2-approximation algorithm for monotone submodular k-set packing and general
k-exchange systems. In 29th International Symposium on Theoretical Aspects of Computer Science.
2012, pp. 42–53.
[70] Z UCKERMAN , D. Linear degree extractors and the inapproximability of max clique and chromatic
number. Theory Comput. 3 (2007), 103–128.

A

Technical Lemmas

In our main section, our algorithm for k -CS-PIP uses the following version of the Chernoff-Hoeffding
bounds. This can be easily derived from the standard form and we give a proof here for completeness.
Theorem 10 (Chernoff-Hoeffding bounds). Suppose c1 , c2 , and k are P
positive values with c2 ≥
X1 , X2 , . . . , Xn ∈ [0, 1] be independent random variables satisfying E[ i Xi ] ≤ ck1 . Then,
 c2
P
c1 e
Pr[ i Xi ≥ c2 ] ≤ kc
2

c1
k.

Let


µ
P
δ
Proof. The standard form of the Chernoff-Hoeffding bounds yields Pr[ i Xi ≥ (1+δ)µ] ≤ (1+δ)e (1+δ) ,

for δ ≥ 0. Note that we want (1 + δ)(c1 /k) = c2 , hence giving 1 + δ =
form of the Chernoff-Hoeffding bounds gives us the desired bound.
28

kc2
c1 .

Plugging this into the standard

Lemma 9 (Convexity). Assume f : [0, 1] → [0, 1] and it has second derivatives over [0, 1]. Then we have
that ln(1 − tf (x)) is a convex function of x ∈ [0, 1] for any given t ∈ (0, 1) iff (1 − f )(−f ′′ ) ≥ f ′2 for all
x ∈ [0, 1].
Proof. Consider a given t ∈ (0, 1) and let F (x) = ln(1 − tf (x)). F (x) is convex over [0, 1] iff F ′′ ≥ 0
for all x ∈ [0, 1]. We can verify that it is equivalent to the condition that (1 − f )(−f ′′ ) ≥ f ′2 for all
x ∈ [0, 1].

B Submodular Functions
In this section, we give the required background needed for submodular functions.
Definition 2 (Submodular functions). A function f : 2[n] → R+
+ on a ground-set of elements [n] :=
{1, 2, . . . , n} is called submodular if for every A, B ⊆ [n], we have that f (A ∪ B) + f (A ∩ B) ≤
f (A) + f (B). Additionally, f is said to be monotone if for every A ⊆ B ⊆ [n], we have that f (A) ≤ f (B).
For our algorithms, we assume a value-oracle access to a submodular function. This means that, there
is an oracle which on querying a subset T ⊆ [n], returns the value f (T ).
Definition 3 (Multi-linear extension). The multi-linear extension of a submodular function f is the continuous function F : [0, 1]n → R+
+ defined as
P
Q
Q
F (x) := T ⊆[n] ( j∈T xj j6∈T (1 − xj ))f (T )

Note that the multi-linear function F (x) = f (x) for every x ∈ {0, 1}n . The multi-linear extension is a
useful tool in maximization of submodular objectives. In particular, the above has the following probabilistic
interpretation. Let S ⊆ [n] be a random subset of items where each item i ∈ [n] is added into S with
probability xi . We then have F (x) = ES∼x [f (S)]. It can be shown that the two definitions of F (x) are
equivalent. Hence, a lower bound on the value of F (x) directly leads to a lower bound on the expected value
of f (S).

29

