=Paper=
{{Paper
|id=Vol-3072/paper3
|storemode=property
|title=A Simple Optimal Contention Resolution Scheme for Uniform Matroids
|pdfUrl=https://ceur-ws.org/Vol-3072/paper3.pdf
|volume=Vol-3072
|authors=Richard Santiago,Danish Kashaev
|dblpUrl=https://dblp.org/rec/conf/ictcs/SantiagoK21
}}
==A Simple Optimal Contention Resolution Scheme for Uniform Matroids==
https://ceur-ws.org/Vol-3072/paper3.pdf
A Simple Optimal Contention Resolution
Scheme for Uniform Matroids ?
Danish Kashaev1 and Richard Santiago2
1
ETH Zürich, Switzerland
danishk@ethz.ch
2
ETH Zürich, Switzerland
rtorres@ethz.ch
Abstract. A common approach to solve a combinatorial optimization
problem is to first solve a continous relaxation and then round the frac-
tional solution. For the latter, the framework of contention resolution
schemes (or CR schemes) introduced by Chekuri, Vondrak, and Zen-
klusen, has become a general and successful tool. A CR scheme takes a
fractional point x in a relaxation polytope, rounds each coordinate xi
independently to get a possibly non-feasible set, and then drops some
elements in order to satisfy the independence constraints. Intuitively, a
CR scheme is c-balanced if every element i is selected with probability
at least c · xi .
It is known that general matroids admit a (1−1/e)-balanced CR scheme,
and that this is (asymptotically) optimal. This is in particular true for
the special case of uniform matroids of rank one. In this work, we provide
a simple and explicit monotone CR scheme with a balancedness factor
of 1 − e−k kk /k! for uniform matroids of rank k (which matches the bal-
ancedness of 1 − 1/e for k = 1), and show that this is optimal. While
this bound can be obtained by combining previously known results, these
require defining an exponential-sized linear program and using random
sampling and the ellipsoid algorithm. Our procedure, on the other hand,
has the advantage of being simple and explicit. Moreover, this scheme
generalizes into an optimal CR scheme for partition matroids.
Keywords: contention resolution schemes · uniform matroids · partition
matroids
1 Introduction
Contention resolution schemes were introduced by Chekuri, Vondrak, and Zen-
klusen [5] as a tool for submodular maximization under various types of con-
straints. A set function f : 2N → R is submodular if for any two sets A ⊂ B ⊂ N
and an element v ∈ / B, the corresponding marginal gains satisfy f (A ∪ {v}) −
f (A) ≥ f (B ∪ {v}) − f (B). Submodular functions are a classical object in com-
binatorial optimization and operations research [11]. Given a finite ground set
?
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 Danish Kashaev and Richard Santiago
N , an independence family I ⊂ 2N and a submodular set function f : 2N 7→ R,
the problem consists of (approximately) solving maxS∈I f (S).
A successful technique to tackle this problem in recent years has been the
relaxation and rounding approach. It consists of first relaxing the discrete prob-
lem into a continuous version maxx∈PI F (x), where F : [0, 1]N 7→ R is a suitable
extension of f , and PI is a relaxation polytope of the independence family I.
One can assume here that PI is the convex hull of all the independent sets,
where every S ∈ I is naturally seen as an element in {0, 1}N . The first step of
the relaxation and rounding approach then approximately solves maxx∈PI F (x)
to obtain a fractional point x ∈ PI .
In order to get a feasible solution to the original problem, we then need
to round this fractional point into an integral and feasible (i.e. independent)
one while keeping the objective value as high as possible. Contention resolu-
tion schemes are a powerful tool to tackle this problem, and have found other
applications outside of submodular maximization.
At the high level, given a fractional point x, the procedure first generates a
random set R(x) by independently including each element i with probability xi .
Since R(x) might not necessarily belong to I, the contention resolution scheme
then removes some elements from it in order to get an independent set. We
denote the support of a point x by supp(x) := {i ∈ N | xi > 0}. A CR scheme
is then formally defined as follows.
Definition 1 (CR scheme). π = (πx )x∈PI is a c-balanced contention resolu-
tion scheme for the polytope PI if for every x ∈ PI , πx is an algorithm that takes
as input a set A ⊂ supp(x) and outputs an independent set πx (A) ∈ I contained
in A such that
h i
P i ∈ πx (R(x)) | i ∈ R(x) ≥ c ∀i ∈ supp(x).
Moreover, a contention resolution scheme is monotone if for any x ∈ PI :
P[i ∈ πx (A)] ≥ P[i ∈ πx (B)] for any i ∈ A ⊂ B ⊂ supp(x).
A c-balanced contention resolution scheme ensures that every element in the
random set R(x) is kept with probability at least c. The goal when designing
CR schemes is thus to maximize this c, that we call the balancedness.
Moreover, monotonicity is a desirable property for a c-balanced CR scheme
to have, since one can then get approximation guarantees for the constrained
submodular maximization problem via the relaxation and rounding approach
(see [5] for more details).
By presenting a variety of CR schemes for different constraints, the work in
[5] gives improved approximation algorithms for linear and submodular maxi-
mization problems under matroid, knapsack, matchoid constraints, as well as
their intersections. There has also been work done for getting CR schemes for
different types of independence families [4, 9], or by having the elements of the
random set R(x) arrive in an online fashion [2, 8, 10, 1]. In this work, we restrict
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 3
our attention to matroid constraints and the offline setting (i.e. we know the full
set R(x) in advance).
A monotone CR scheme with a balancedness of 1−(1−1/n)n for the uniform
matroid of rank one is given in [6, 7], where it is also shown that this is optimal.
That is, there is no c-balanced CR scheme for the uniform matroid of rank one
with c > 1 − (1 − 1/n)n . The work of [5] extends this result by proving the
existence of a monotone 1 − (1 − 1/n)n -balanced CR scheme for any matroid.
This requires defining an exponential-sized linear program and using its dual.
The existence argument can then be turned into an efficient algorithm by using
random sampling and the ellipsoid algorithm to construct a CR scheme with a
balancedness of 1 − 1/e, which is asymptotically optimal.
By using a reduction from the previously mentioned existence proof ([5, see
Theorem 4.3]) and a recent result from [3], one can prove the existence of a
(1 − e−k k k /k!)-balanced CR scheme for the uniform matroid of rank k (i.e. car-
dinality constraints). The main drawback of this approach is, however, its lack
of simplicity. In a different context, another procedure which may be interpreted
as a monotone CR √ scheme for cardinality constraints with a slightly worse bal-
ancedness of 1 − 1/ k + 3 is shown in [2].
1.1 Our contributions
Our main result is to provide a simple, explicit, and optimal monotone CR
scheme for the uniform matroid of rank k on n elements, with a balancedness of
n+1−k k k
c(k, n) := 1 − nk 1 − nk
n . This result is encapsulated in Theorem 1
(balancedness), Theorem 4 (optimality), and Theorem 5 (monotonicity). This
generalizes the balancedness factor of 1−(1−1/n)n given in [6, 7] for the rank one
(i.e. k = 1) case. Moreover, for a fixed value of k, we have that c(k, n) converges
from above to 1 − e−k k k /k!. While it is possible to prove the existence of a
(1−e−k k k /k!)-balanced CR scheme by combining results from [5, 3], these require
defining an exponential-sized linear program and using its dual. In addition, to
turn this existence proof into an actual algorithm, one needs to use random
sampling and the ellipsoid algorithm. The advantage of our CR scheme is thus
that it is a very simple and explicit procedure. Moreover, our balancedness is an
explicit formula which also depends on n (the number of elements) in addition
to k, and c(k, n) > 1 − e−k k k /k! for every fixed n.
We also discuss how the above CR scheme for uniform matroids naturally
generalizes to partition matroids. If we denote by c(k, n) the optimal balanced-
ness for uniform matroids of rank k, then the balancedness we get for partition
matroids with blocks Di and capacities di is mini c(di , |Di |), and this is optimal.
Due to the space constraints, we omit the discussion on partition matroids from
this version, but it can be found in the full version available on ArXiv.
4 Danish Kashaev and Richard Santiago
1.2 Preliminaries on matroids
In this section we provide a brief background on matroids. A matroid M is a
pair (N, I) consisting of a ground set N and a non-empty family of independent
sets I ⊂ 2N which satisfy:
– If A ∈ I and B ⊂ A, then B ∈ I.
– If A ∈ I and B ∈ I with |A| > |B|, then ∃ i ∈ A\B such that B ∪ {i} ∈ I.
Given a matroid M = (N, I) its rank function r : 2N → R≥0 is defined as r(A) =
max{|S| : S ⊆ A, S ∈ I}. Its matroid polytope is given by PIP:= conv({1S : S ∈
I}) = {x ∈ RN ≥0 : x(A) ≤ r(A), ∀A ⊂ N }, where x(A) := i∈A xi . Note that
the definition implies that xi ∈ [0, 1] for every i ∈ N .
The next two classes of matroids are of special interest for this work.
Example 1 (Uniform matroid). The uniform matroid of rank k on n elements
Unk := (N, I) is the matroid whose independent sets are all the subsets of the
ground set of cardinality at most k. That is, I := {A ⊂ N : |A| ≤ k}.
Example 2 (Partition matroid). Partition matroids are a generalization of uni-
form matroids. Suppose the ground set is partitioned into k blocks: N = D1 ]
· · · ] Dk and each block Di has a certain capacity di ∈ Z≥0 . Then I := {A ⊂
N : |A ∩ Di | ≤ di , ∀i ∈ {1, . . . , k}}. The uniform matroid Unk is simply a par-
tition matroid with one block N and one capacity k. Moreover, the restriction
of a partition matroid to each block Di is a uniform matroid of rank di on the
ground set Di .
2 An optimal monotone contention resolution scheme for
uniform matroids
We assume throughout that n ≥ 2 and k ∈ {1, . . . , n − 1}. For any point x ∈ PI ,
we let R(x) be the random set satisfying P[i ∈ R(x)] = xi independently for each
coordinate. If the size of R(x) is at most k, then R(x) is already an independent
set and the CR scheme returns it. If however |R(x)| > k, then the CR scheme
returns a random subset of k elements by making the probabilities of each subset
of k elements depend linearly on the coordinates of the original point x ∈ PI .
More precisely, given an arbitrary x ∈ PI , for any set A ⊂ supp(x) with |A| > k
and any subset B ⊂ A of size k, we define
1
qA (B) := |A| 1 + x̄(A \ B) − x̄(B) , (1)
|B|
where we use the following notation: x̄(A) := x(A) 1
P
|A| = |A| i∈A xi . We then define
k
a randomized CR scheme π for Un as follows.
Algorithm 1 (CR scheme π for Unk ) We are given a point x ∈ PI and a set
A ⊂ supp(x). If |A| ≤ k, then πx (A) = A. If |A| > k, then for every B ⊂ A with
|B| = k, πx (A) = B with probability qA (B).
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 5
One can check that this CR scheme is well-defined, i.e. that qA is a valid
probability distribution.
Lemma 1. The above procedure π is a well-defined
P CR scheme. That is, ∀x ∈
PI and A ⊂ supp(x), we have qA (B) ≥ 0 and B⊂A,|B|=k qA (B) = 1.
The next result gives an explicit formula for the marginal probabilities of the
distribution qA .
Lemma 2. The following holds for any e ∈ A and |A| > k:
k − xe x(A \ e)
P[e ∈ πx (A)] = + .
|A| |A|(|A| − 1)
We now state our main result.
Theorem 1. Algorithm 1 is a c-balanced CR scheme for the uniform matroid
n+1−k k k
of rank k on n elements, where c = 1 − nk 1 − nk
n .
Since we use the above expression often throughout this section, we denote it by
n+1−k k
n k k
c(k, n) := 1 − 1− .
k n n
We note that when k = 1 we get c(1, n) = 1 − (1 − 1/n)n , which matches the
optimal balancedness for Un1 provided in [6, 7]. This converges to 1 − 1/e when n
gets large. In addition, the balancedness factor improves as k grows. Indeed, our
next result shows that for any k > 1, the balancedness c(k, n) is asymptotically
(as n grows) strictly better than 1 − 1/e.
Proposition 1 For a fixed k, the limit of c(k, n) as n tends to infinity is
kk
lim c(k, n) = 1 − e−k .
n→∞ k!
2.1 Outline of the proof of Theorem 1
Throughout this whole section on uniform matroids, we fix an arbitrary element
e ∈ N . In order to prove Theorem 1, we need to show that for every x ∈ PI
with xe > 0 we have P[e ∈ πx (R(x)) | e ∈ R(x)] ≥ c(k, n). This is equivalent to
showing that for every x ∈ PI with xe > 0 we have
P[e ∈
/ πx (R(x)) | e ∈ R(x)] ≤ 1 − c(k, n). (2)
We now introduce some definitions and notation Q
that willQbe needed. For
any B ⊂ A ⊂ N , let pA (B) := P[RA (x) = B] = i∈B xi i∈A\B (1 − xi ),
where RA (x) is the random set obtained by rounding each coordinate of x|A
in the reduced ground set A to one independently with probability xi . Note
that pN (B) = P[R(x) = B]. We do not write the dependence on x ∈ PI for
6 Danish Kashaev and Richard Santiago
simplicity of notation. We mainly work on the set N \ {e}. For this reason, we
define S := N \ {e}. Note that |S| = n − 1; we use this often in our arguments.
With the above notation we can rewrite the probability in (2) in a more
convenient form. For any x ∈ PI satisfying xe > 0, we get
h i
P e∈
/ πx (R(x)) | e ∈ R(x)
X
= P[e ∈
/ πx (R(x)) | RS (x) = A, e ∈ R(x)] P[RS (x) = A | e ∈ R(x)]
A⊂S
X h i
= P e∈
/ πx (R(x)) | R(x) = A ∪ e pS (A)
A⊂S,|A|≥k
X X
= pS (A) qA∪e (B).
A⊂S,|A|≥k B⊂A,|B|=k
The obtained expression is a multivariable function of the variables x1 , . . . , xn ,
since pS (A) and qA∪e (B) depend on those variables as well. We denote it by
X X
G(x) := pS (A) qA∪e (B). (3)
A⊂S,|A|≥k B⊂A,|B|=k
One then has that for proving Theorem 1 it is enough to show the following.
Theorem 2. Let G(x) and c(k, n) be as defined above. Then maxx∈PI G(x) =
1 − c(k, n). Moreover, the maximum is attained at the point (x1 , . . . , xn ) =
(k/n, . . . , k/n) ∈ PI .
Indeed, Theorem 2 implies that for every x ∈ PI we have G(x) ≤ 1 −
c(k, n), with equality holding if x = (k/n, . . . , k/n). In particular, for any x ∈ PI
satisfying xe > 0, we get
h i
G(x) = P e ∈
/ πx (R(x)) | e ∈ R(x) ≤ 1 − c(k, n),
which proves Theorem 1 by (2).
Notice that for the conditional probability to be well defined, we need the
assumption that xe > 0. However, in our case G(x) is simply a multivariable
polynomial function of the n variables x1 , . . . , xn and is thus also defined when
xe = 0. We may therefore forget the conditional probability and simply treat
Theorem 2 as a multivariable maximization problem over a bounded domain.
We now state the outline of the proof for Theorem 2.
We first maximize G(x) over the variable xe , and get an expression depending
only on the x-variables in S. This is done in Section 2.2. We then maximize the
above expression over the unit hypercube [0, 1]S (see Section 2.3). Finally, we
combine the above two results to show that the maximum in Theorem 2 is
attained at the point xi = k/n for every i ∈ N ; this is done in Section 2.4.
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 7
2.2 Maximizing over the variable xe
The matroid polytope of Unk is given by PI = {x ∈ [0, 1]N : x(N ) ≤ k}. We
define a new polytope by removing the constraint xe ≤ 1 from PI :
PeI := {x ∈ RN
≥0 : x(N ) ≤ k and xi ≤ 1 ∀i ∈ S}.
Clearly, PI ⊂ PeI .
We now present the main result of this section, where we consider the max-
imization problem max{G(x) | x ∈ PeI } and maximize G(x) over the variable
xe while keeping all the other variables (xi for every i ∈ S) fixed to get an
expression depending only on the x-variables in S.
Lemma 3. For every x ∈ PeI ,
X
G(x) ≤ pS (A) 1 − x̄(A) . (4)
A⊂S,|A|=k
Moreover, equality holds when xe = k − x(S).
2.3 Maximizing hkS : [0, 1]S 7→ R
In this section we turn our attention into maximizing the right-hand side expres-
sion in (4) over the unit hypercube [0, 1]S . In fact, we work with the following
function instead: X
hkS (x) := pS (A)(k − x(A)).
A⊂S
|A|=k
A plot of hkS (x) for S = {1, 2} and k = 1, 2 is presented in Figure 1. Note that
the above function is simply the right hand side of (4) multiplied by k. Hence,
maximizing one or the other is equivalent.
Theorem 3. Let n ≥ 2, so that |S| = n − 1 ≥ 1 and k ∈ {1, . . . , n − 1}. Then
the function hkS (x) attains its maximum over the unit hypercube [0, 1]S at the
point (k/n, . . . , k/n) with value
n+1−k k
n k k
hkS k/n, . . . , k/n = k 1− = k 1 − c(k, n) .
k n n
For simplicity, we denote this maximum value by:
n+1−k k
n k k
α(k, n) := k 1− .
k n n
Notice that h0S (x) = hnS (x) = 0 for any x ∈ [0, 1]S . Hence Theorem 3 holds
for k = 0 and k = n as well. Moreover, the function hkS (x) also satisfies an
interesting duality property: hkS (x) = hn−k
S (1 − x).
8 Danish Kashaev and Richard Santiago
(a) S = {1, 2}, k = 1 (b) S = {1, 2}, k = 2
Fig. 1: Plot of hkS (x) for S = {1, 2}. The maximum is attained at x1 = x2 = 1/3
in (a) and at x1 = x2 = 2/3 in (b).
In order to prove Theorem 3, we first show that h has a unique extremum (in
particular a local maximum) in the interior of [0, 1]S at the point (k/n, . . . , k/n)
— see Proposition 2. We then use induction on n to show that any point in
the boundary of [0, 1]S has a lower function value than hkS (k/n, . . . , k/n). Since
our function is continuous over a compact domain, it attains a maximum. That
maximum then has to be attained at (k/n, . . . , k/n) by the two arguments above.
That is, the unique extremum cannot be a local minimum or a saddle point.
Otherwise, since there are no more extrema in the interior and the function is
continuous, the function would increase in some direction leading to a point in the
boundary having higher value. In the full version of the paper we also present an
alternative proof for showing local maximality that relies on the Hessian matrix.
Proposition 2 For any k ∈ {1, . . . , n − 1}, hkS (x) has a unique extremum in the
interior of the unit hypercube [0, 1]S at the point (k/n, . . . , k/n).
We need the following lemma in order to prove Proposition 2.
Lemma 4. The following holds for any x ∈ [0, 1]S :
k−1
X
hkS (x) = QiS (x) x(S) − i
i=0
where X
QkS (x) := pS (A).
A⊂S,|A|=k
The above formula actually holds for hkA with any A ⊂ N . We use this in
Section 2.5 with A = N . We need one additional lemma before being able to
prove Theorem 3.
Lemma 5. The following holds for any n ≥ 2 and k ∈ {1, . . . , n − 1}:
α(k, n) > α(k − 1, n − 1), (5)
α(k, n) > α(k, n − 1). (6)
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 9
We are now ready to prove Theorem 3.
Proof (Proof of Theorem 3). We prove the statement by induction on n ≥ 2.
The base case corresponds to n = 2 and k = 1. In this case, we get S = {1}
and hkS (x) = x1 (1 − x1 ). It is easy to see that this is a parabola which attains
its maximum at the point x1 = 1/2 over the unit interval [0, 1]. Moreover the
function value at that point is 1/4 = α(1, 2).
We now prove the induction step. Let n ≥ 3 and k ∈ {1, . . . , n − 1}, and
assume by induction hypothesis that the statement holds for any 2 ≤ n0 < n
and k ∈ {1, 2, . . . , n0 − 1}.
By Proposition 2, hkS (x) has a unique extremum in the interior of [0, 1]S at
the point (k/n, . . . , k/n). We first show that the function hkS (x) evaluated at
that point is indeed equal to α(k, n).
k n−1−k
k n−1 k k k
hS (k/n, . . . , k/n) = 1− k−k
k n n n
k n−k
n−1 k k
=k 1−
k n n (7)
k n−k
n−k n k k
=k 1−
n k n n
= α(k, n).
We next show that any point on the boundary of [0, 1]S has a lower function
value than α(k, n). A point x ∈ [0, 1]S lies on the boundary if there exists i ∈ S
such that xi = 0 or xi = 1.
– Suppose there exists i ∈ S such that xi = 0. For any set A ⊂ S containing
i, we get pS (A) = 0. Hence:
X X
hkS (x) = pS (A)(k − x(A)) = pS\i (A)(k − x(A)) = hkS\i (x).
A⊂S,|A|=k A⊂S\i,|A|=k
If k = n − 1, then hkS\i (x) = 0. We then clearly get hkS (x) = hkS\i (x) = 0 <
α(k, n). If k < n − 1, then by induction hypothesis and Lemma 5,
hkS (x) = hkS\i (x) ≤ α(k, n − 1) < α(k, n).
– Suppose there exists i ∈ S such that xi = 1. For any set A ⊂ S not containing
i, we get pS (A) = 0. Hence:
X X
hkS (x) = pS (A)(k − x(A)) = pS (A)(k − x(A))
A⊂S,|A|=k A⊂S
|A|=k
i∈A
X X
= pS\i (A \ i)(k − 1 − x(A \ i)) = pS\i (A)(k − 1 − x(A))
A⊂S A⊂S\i
|A|=k |A|=k−1
i∈A
= hk−1
S\i (x).
10 Danish Kashaev and Richard Santiago
If k = 1, then hk−1 k k−1
S\i (x) = 0. We then clearly get hS (x) = hS\i (x) = 0 <
α(k, n). If k > 1, then by induction hypothesis and Lemma 5,
hkS (x) = hk−1
S\i (x) ≤ α(k − 1, n − 1) < α(k, n).
Since our function is continuous over a compact domain, it attains a maximum.
By using continuity, together with the facts that (k/n, . . . , k/n) is the unique
extremum in the interior, and that it has higher function value than any point
at the boundary, it follows that (k/n, . . . , k/n) must be a global maximum. This
completes the proof.
2.4 Proof of Theorem 1
We now have all the ingredients to prove Theorem 2 and, therefore, Theorem 1.
The two main building blocks for the proof are Lemma 3 and Theorem 3.
Proof (Proof of Theorem 2). By Lemma 3, we get that for any x ∈ PI (since
PI ⊂ PeI ), X
G(x) ≤ pS (A)(1 − x̄(A)). (8)
A⊂S
|A|=k
Moreover, for every x ∈ PI satisfying xe = k − x(S), equality holds in (8).
By Theorem 3, we get that for any x ∈ PI ,
X
pS (A)(1 − x̄(A)) ≤ 1 − c(k, n). (9)
A⊂S
|A|=k
Equality holds in (9) if xi = k/n for every i ∈ S. This holds because the above
expression does not depend on xe , and the projection of the polytope PI to the
S coordinates is included in the unit hypercube [0, 1]S .
Therefore, by combining (8) and (9), we get that G(x) ≤ 1 − c(k, n) for
every x ∈ PI . Moreover, for the point xi = k/n for every i ∈ N , equality
holds: G(k/n, . . . , k/n) = 1 − c(k, n). Indeed, (8) holds with equality because
xe = k − x(S) is satisfied (since k − x(S) = k − (n − 1)k/n = k/n), and (9) also
holds with equality because xi = k/n for every i ∈ S.
2.5 Optimality
In this section, we argue that Algorithm 1 is in fact optimal for Unk .
Theorem 4. There does not exist a c-balanced CR scheme for the uniform ma-
n+1−k k k
troid of rank k on n elements satisfying c > 1 − nk 1 − nk
n .
The proof uses a similar
argument
to the one used for Un1 in [5]. It relies on
computing the value E r(R(x) , i.e. the expected rank of the random set R(x).
However, for general values of k > 1, the argument becomes more involved than
the one presented in [5] for Un1 . The proof we present uses Lemma 4.
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 11
Corollary 1 (of Lemma 4). Let x ∈ PI be the point xi = k/n for all i ∈ N .
Pk−1
Then hkN (x) = i=0 QiN (x)(k − i).
Proof (Proof of Theorem 4). Let π be an arbitrary c-balanced CR scheme for
Unk , and fix the point x such that xi = nk for every i ∈ N. Clearly, x ∈ PI = {x ∈
[0, 1]N : x1 +· · ·+xn ≤ k}. Let R(x) be the random set satisfying P[i ∈ R(x)] = xi
for each i independently, and denote by I := πx (R(x)) the set returned by
the CR scheme π. By definition of a CR scheme, we have E[|I|] ≤ E r(R(x))
nck
P P
and
E[|I|] = i∈N P[i ∈ I] ≥ i∈N c xi = n = ck. It follows that c ≤
E r(R(x)) /k. Moreover, recall that
X
P[|R(x)| = i] = pN (A) = QiN (x). (10)
A⊂N
|A|=i
We then have
k
X k−1
X
E[r(R(x))] = i P[r(R(x)) = i] = i P |R(x)| = i + k P |R(x)| ≥ k
i=0 i=0
k−1
X
= i P |R(x)| = i + k 1 − P |R(x)| ≤ k − 1
i=0
k−1
X k−1
X
=k+ i P |R(x)| = i − k P |R(x)| = i
i=0 i=0
k−1
X
=k− (k − i)QiN (x) by (10)
i=0
= k − hkN (x) by Corollary 1
X
=k− pN (A)(k − x(A))
A⊂N,|A|=k
k n−k
kX k k
=k− 1− k−k
n n n
A⊂N,|A|=k
n+1−k k !
n k k
=k 1− 1− .
k n n
Combining this with the bound c ≤ E r(R(x)) /k leads to the desired result.
2.6 Monotonicity
We next argue that Algorithm 1 is a monotone CR scheme. This is a desirable
property for CR schemes, since then they can be used to derive approximation
guarantees for constrained submodular maximization problems.
12 Danish Kashaev and Richard Santiago
Theorem 5. Algorithm 1 is a monotone CR scheme for Unk . That is, for every
x ∈ PI and e ∈ A ⊂ B ⊂ supp(x), we have P[e ∈ πx (A)] ≥ P[e ∈ πx (B)].
Proof. Let A ⊂ N and e ∈ A. If |A| ≤ k, then P[e ∈ πx (A)] = 1, and the
theorem trivially holds. We therefore suppose that |A| > k. In order to prove
the theorem, it is clearly enough to show that for any f ∈
/ A,
P[e ∈ πx (A)] ≥ P[e ∈ πx (A ∪ f )]. (11)
We show the difference of those two terms is greater than 0 by using Lemma 2
for both terms:
k − xe x(A \ e) k − xe x(A \ e) + xf
P[e ∈ πx (A)] − P[e ∈ πx (A ∪ f )] = + − −
|A| |A|(|A| − 1) |A| + 1 (|A| + 1)|A|
k − xe k − xe xf 1 1
= − − + x(A \ e) −
|A| |A| + 1 (|A| + 1)|A| |A|(|A| − 1) (|A| + 1)|A|
(|A| + 1)(k − xe ) − |A|(k − xe ) − xf 2x(A \ e)
= +
|A|(|A| + 1) (|A|2 − 1)|A|
k − xe − xf 2x(A \ e)
= + ≥ 0.
|A|(|A| + 1) (|A|2 − 1)|A|
The last inequality holds because since x ∈ PI = {x ∈ [0, 1]N | x(N ) ≤ k}, we
have xe + xf ≤ k, and all the other terms are positive. We have thus shown (11)
which is enough to prove the theorem.
3 Conclusion
Contention resolution schemes are a general and powerful tool for rounding
a fractional point in a relaxation polytope. It is known that matroids admit
(1 − 1/e)-balanced CR schemes, and that this is the best possible. This impossi-
bility result is in particular true for uniform matroids of rank one. For uniform
matroids of rank k (i.e. cardinality constraints), one can get a (1 − e−k k k /k!)-
balanced CR scheme by combining a reduction from [5] and a recent result from
[3]. The main drawback of this approach, however, is its lack of simplicity: the ex-
istence proof requires defining an exponential sized linear program and using its
dual. Moreover, turning this existence proof into an algorithm requires random
sampling and the ellipsoid algorithm. We provide in this work a much simpler
n+1−k k k
and explicit scheme with a balancedness of c(k, n) := 1− nk 1 − nk
n .
In particular, c(k, n) > 1 − e−k k k /k! for every n, and c(k, n) converges to
1 − e−k k k /k! as n goes to infinity. Our balancedness is therefore better for every
fixed n, and achieves 1 − e−k k k /k! asymptotically. We also show optimality and
monotonicity of our scheme.
Acknowledgements We thank Chandra Chekuri and Vasilis Livanos for useful
feedback, and for pointing out the connection with the work of [3].
A Simple Optimal Contention Resolution Scheme for Uniform Matroids 13
References
1. Adamczyk, M., Wlodarczyk, M.: Random order contention resolution schemes. In:
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS).
pp. 790–801. IEEE (2018)
2. Alaei, S.: Bayesian combinatorial auctions: Expanding single buyer mechanisms to
many buyers. SIAM Journal on Computing 43(2), 930–972 (2014)
3. Barman, S., Fawzi, O., Ghoshal, S., Gürpınar, E.: Tight approximation bounds for
maximum multi-coverage. Mathematical Programming pp. 1–34 (2021)
4. Bruggmann, S., Zenklusen, R.: An optimal monotone contention resolution scheme
for bipartite matchings via a polyhedral viewpoint. Mathematical Programming
pp. 1–51 (2020)
5. Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via
the multilinear relaxation and contention resolution schemes. SIAM Journal on
Computing 43(6), 1831–1879 (2014)
6. Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: Improv-
ing the factor of 1-1/e. In: 2006 47th Annual IEEE Symposium on Foundations of
Computer Science (FOCS’06). pp. 667–676. IEEE (2006)
7. Feige, U., Vondrák, J.: The submodular welfare problem with demand queries.
Theory of Computing 6(1), 247–290 (2010)
8. Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes.
In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete
algorithms. pp. 1014–1033. SIAM (2016)
9. Guruganesh, G., Lee, E.: Understanding the correlation gap for matchings. In: 37th
IARCS Annual Conference on Foundations of Software Technology and Theoret-
ical Computer Science (FSTTCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer
Informatik (2018)
10. Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante
prophet inequalities. In: 26th Annual European Symposium on Algorithms (ESA
2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
11. Lovász, L.: Submodular functions and convexity. In: Mathematical Programming
The State of the Art, pp. 235–257. Springer (1983)