A common approach to solve a combinatorial optimization problem is to rst solve a continous relaxation and then round the fractional solution. For the latter, the framework of contention resolution schemes (or CR schemes) introduced by Chekuri, Vondrak, and Zenklusen, 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 kkk=k! for uniform matroids of rank k (which matches the balancedness 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 de ning 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.
Contention resolution schemes were introduced by Chekuri, Vondrak, and
Zenklusen [
Commons License Attribution 4.0 International (CC BY 4.0). N , an independence family I 2N and a submodular set function f : 2N 7! R, the problem consists of (approximately) solving maxS2I f (S).
A successful technique to tackle this problem in recent years has been the relaxation and rounding approach. It consists of rst relaxing the discrete problem into a continuous version maxx2PI 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 2 I is naturally seen as an element in f0; 1gN . The rst step of the relaxation and rounding approach then approximately solves maxx2PI F (x) to obtain a fractional point x 2 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 resolution 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 rst 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) := fi 2 N j xi > 0g. A CR scheme is then formally de ned as follows.
De nition 1 (CR scheme). = ( x)x2PI is a c-balanced contention resolution scheme for the polytope PI if for every x 2 PI , x is an algorithm that takes as input a set A supp(x) and outputs an independent set x(A) 2 I contained in A such that
h P i 2 x(R(x)) j i 2 R(x) i c 8i 2 supp(x): Moreover, a contention resolution scheme is monotone if for any x 2 PI : P[i 2 x(A)]
P[i 2 x(B)] for any i 2 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 [
By presenting a variety of CR schemes for di erent constraints, the work in
[
A monotone CR scheme with a balancedness of 1 (1 1=n)n for the uniform
matroid of rank one is given in [
By using a reduction from the previously mentioned existence proof ([5, see
Theorem 4.3]) and a recent result from [
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
c(k; n) := 1 nk 1 nk n+1 k nk k. 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 [
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 balancedness for uniform matroids of rank k, then the balancedness we get for partition matroids with blocks Di and capacities di is mini c(di; jDij), 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.
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 2 I and B A, then B 2 I.
{ If A 2 I and B 2 I with jAj > jBj, then 9 i 2 AnB such that B [ fig 2 I. Given a matroid M = (N; I) its rank function r : 2N ! R 0 is de ned as r(A) = maxfjSj : S A; S 2 Ig. Its matroid polytope is given by PI := conv(f1S : S 2 Ig) = fx 2 RN0 : x(A) r(A); 8A N g, where x(A) := Pi2A xi. Note that the de nition implies that xi 2 [0; 1] for every i 2 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 := fA N : jAj kg. Example 2 (Partition matroid). Partition matroids are a generalization of uniform matroids. Suppose the ground set is partitioned into k blocks: N = D1 ] ] Dk and each block Di has a certain capacity di 2 Z 0. Then I := fA N : jA \ Dij di; 8i 2 f1; : : : ; kgg. The uniform matroid Unk is simply a partition 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 2 f1; : : : ; n 1g. For any point x 2 PI , we let R(x) be the random set satisfying P[i 2 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 jR(x)j > 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 2 PI . More precisely, given an arbitrary x 2 PI , for any set A supp(x) with jAj > k and any subset B A of size k, we de ne 1 jAj jBj qA(B) := 1 + x(A n B) x(B) ; (1) where we use the following notation: x(A) := xj(AAj) = j A1j Pi2A xi. We then de ne a randomized CR scheme for Unk as follows.
Algorithm 1 (CR scheme for Unk) We are given a point x 2 PI and a set A supp(x). If jAj k, then x(A) = A. If jAj > k, then for every B A with jBj = k; x(A) = B with probability qA(B).
One can check that this CR scheme is well-de ned, i.e. that qA is a valid probability distribution.
Lemma 1. The above procedure is a well-de ned CR scheme. That is, 8x 2 PI and A supp(x), we have qA(B) 0 and PB A;jBj=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 2 A and jAj > k:
P[e 2 x(A)] = k
xe + A j j
x(A n e) jAj(jAj 1) :
Theorem 1. Algorithm 1 is a c-balanced CR scheme for the uniform matroid
of rank k on n elements, where c = 1 nk 1 nk n+1 k nk k.
Since we use the above expression often throughout this section, we denote it by
c(k; n) := 1
n
k
1
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 [
Proposition 1 For a xed k, the limit of c(k; n) as n tends to in nity is lim c(k; n) = 1 n!1 e k kk : k! 2.1
Throughout this whole section on uniform matroids, we x an arbitrary element e 2 N . In order to prove Theorem 1, we need to show that for every x 2 PI with xe > 0 we have P[e 2 x(R(x)) j e 2 R(x)] c(k; n). This is equivalent to showing that for every x 2 PI with xe > 0 we have
P[e 2= x(R(x)) j e 2 R(x)] 1
We now introduce some de nitions and notation that will be needed. For any B A N , let pA(B) := P[RA(x) = B] = Qi2B xi Qi2AnB(1 xi), where RA(x) is the random set obtained by rounding each coordinate of xjA 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 2 PI for simplicity of notation. We mainly work on the set N n feg. For this reason, we de ne S := N n feg. Note that jSj = 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 2 PI satisfying xe > 0, we get
h P e 2= x(R(x)) j e 2 R(x)
i = = X P[e 2= x(R(x)) j RS(x) = A; e 2 R(x)] P[RS(x) = A j e 2 R(x)] A S
X
h i
P e 2= x(R(x)) j R(x) = A [ e pS(A) =
A S;jAj k
X A S;jAj k pS(A)
X B A;jBj=k
qA[e(B): 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 G(x) :=
X A S;jAj k pS(A)
X B A;jBj=k qA[e(B): (3) 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 de ned above. Then maxx2PI G(x) = 1 c(k; n). Moreover, the maximum is attained at the point (x1; : : : ; xn) = (k=n; : : : ; k=n) 2 PI :
Indeed, Theorem 2 implies that for every x 2 PI we have G(x) 1 c(k; n), with equality holding if x = (k=n; : : : ; k=n). In particular, for any x 2 PI satisfying xe > 0, we get
h G(x) = P e 2= x(R(x)) j e 2 R(x) i 1 c(k; n); which proves Theorem 1 by (2).
Notice that for the conditional probability to be well de ned, 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 de ned 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 rst 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 2 N ; this is done in Section 2.4.
The matroid polytope of Unk is given by PI = fx 2 [0; 1]N : x(N ) de ne a new polytope by removing the constraint xe 1 from PI : kg. We PeI := fx 2 RN0 : x(N ) k and xi 1 8i 2 Sg: Clearly, PI PeI .
We now present the main result of this section, where we consider the maximization problem maxfG(x) j x 2 PeI g and maximize G(x) over the variable xe while keeping all the other variables (xi for every i 2 S) xed to get an expression depending only on the x-variables in S.
Lemma 3. For every x 2 PeI ,
G(x) pS (A) 1 x(A) : (4) Moreover, equality holds when xe = k x(S). 2.3
Maximizing hkS : [0; 1]S 7! R
X A S;jAj=k
A S jAj=k In this section we turn our attention into maximizing the right-hand side expression in (4) over the unit hypercube [0; 1]S . In fact, we work with the following function instead: hkS (x) :=
X pS (A)(k x(A)): A plot of hkS (x) for S = f1; 2g 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 jSj = n 1 1 and k 2 f1; : : : ; n 1g. Then the function hkS (x) attains its maximum over the unit hypercube [0; 1]S at the point (k=n; : : : ; k=n) with value hkS k=n; : : : ; k=n = k = k 1 c(k; n) : For simplicity, we denote this maximum value by: (k; n) := k n k
1 n k k n 1 n+1 k k k n k n n+1 k k k n : Notice that h0S (x) = hSn (x) = 0 for any x 2 [0; 1]S . Hence Theorem 3 holds for k = 0 and k = n as well. Moreover, the function hkS (x) also satis es an interesting duality property: hkS (x) = hSn k(1 x). (a) S = f1; 2g; k = 1 (b) S = f1; 2g; k = 2
In order to prove Theorem 3, we rst 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 2 f1; : : : ; n 1g; 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 2 [0; 1]S : where
k 1 hkS (x) = X QiS (x) x(S)
i i=0 QkS (x) :=
X A S;jAj=k pS (A): 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 2 f1; : : : ; n
1g: (k; n) > (k; n) > (k (k; n 1; n
1); 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 = f1g 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 2 f1; : : : ; n 1g, and assume by induction hypothesis that the statement holds for any 2 n0 < n and k 2 f1; 2; : : : ; n0 1g.
By Proposition 2, hkS(x) has a unique extremum in the interior of [0; 1]S at the point (k=n; : : : ; k=n). We rst show that the function hkS(x) evaluated at that point is indeed equal to (k; n).
hkS(k=n; : : : ; k=n) = hkS(x) =
X A S;jAj=k A S jAj=k i2A = hkSni1(x): We next show that any point on the boundary of [0; 1]S has a lower function value than (k; n). A point x 2 [0; 1]S lies on the boundary if there exists i 2 S such that xi = 0 or xi = 1.
{ Suppose there exists i 2 S such that xi = 0. For any set A i, we get pS(A) = 0. Hence:
hkS(x) =
X A S;jAj=k
X
A Sni;jAj=k pS(A)(k x(A)) = pSni(A)(k x(A)) = hkSni(x): If k = n 1, then hkSni(x) = 0. We then clearly get hkS(x) = hkSni(x) = 0 < (k; n). If k < n 1, then by induction hypothesis and Lemma 5, hkS(x) = hkSni(x) (k; n If k = 1, then hkSni1(x) = 0. We then clearly get hkS(x) = hkSni1(x) = 0 < (k; n): If k > 1, then by induction hypothesis and Lemma 5, hkS(x) = hkSni1(x) (k 1; 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. 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 2 PI (since PI PeI ),
G(x)
X pS(A)(1
x(A)): Moreover, for every x 2 PI satisfying xe = k
By Theorem 3, we get that for any x 2 PI , x(S), equality holds in (8).
X pS(A)(1 Equality holds in (9) if xi = k=n for every i 2 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 2 PI . Moreover, for the point xi = k=n for every i 2 N , equality
holds: G(k=n; : : : ; k=n) = 1 c(k; n): Indeed, (8) holds with equality because
xe = k x(S) is satis ed (since k x(S) = k (n 1)k=n = k=n), and (9) also
holds with equality because xi = k=n for every i 2 S.
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
matroid of rank k on n elements satisfying c > 1 nk 1 nk n+1 k nk k.
The proof uses a similar argument to the one used for Un1 in [
Proof (Proof of Theorem 4). Let be an arbitrary c-balanced CR scheme for Unk, and x the point x such that xi = nk for every i 2 N: Clearly, x 2 PI = fx 2 [0; 1]N : x1+ +xn kg. Let R(x) be the random set satisfying P[i 2 R(x)] = xi for each i independently, and denote by I := x(R(x)) the set returned by the CR scheme . By de nition of a CR scheme, we have E[jIj] E r(R(x)) and E[jIj] = Pi2N P[i 2 I] Pi2N c xi = nnck = ck. It follows that c E r(R(x)) =k. Moreover, recall that
P[jR(x)j = i] =
X pN (A) = QiN (x): A N jAj=i
k k 1 E[r(R(x))] = X i P[r(R(x)) = i] = X i P jR(x)j = i + k P jR(x)j i=0 i=0 k 1 = X i P jR(x)j = i + k 1 P jR(x)j k 1 i=0 k (10) k 1 = k + X i P jR(x)j = i i=0 k 1 = k X(k i)QiN (x) = k = k = k = k 1 i=0 hkN (x) A N;jAj=k A N;jAj=k
X X n k pN (A)(k
x(A)) k k n 1 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. Theorem 5. Algorithm 1 is a monotone CR scheme for Unk. That is, for every x 2 PI and e 2 A B supp(x), we have P[e 2 x(A)] P[e 2 x(B)]: Proof. Let A N and e 2 A. If jAj k, then P[e 2 x(A)] = 1, and the theorem trivially holds. We therefore suppose that jAj > k. In order to prove the theorem, it is clearly enough to show that for any f 2= A,
P[e 2 x(A)]
P[e 2 x(A [ f )]: (11) We show the di erence of those two terms is greater than 0 by using Lemma 2 for both terms: P[e 2 x(A)]
P[e 2 x(A [ f )] = k
xe =
A j j = (jAj + 1)(k = k xe xf + jAj(jAj + 1) k xe
xf jAj + 1
(jAj + 1)jAj xe) jAj(k xe) jAj(jAj + 1)
2x(A n e) (jAj2 1)jAj
0: k
A j j xe +
x(A n e) jAj(jAj k
xe jAj + 1 + x(A n e) xf + 1)
1 jAj(jAj 2x(A n e) (jAj2 1)jAj x(A n e) + xf (jAj + 1)jAj 1 1) (jAj + 1)jAj The last inequality holds because since x 2 PI = fx 2 [0; 1]N j x(N ) kg, 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
impossibility 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
kkk=k!)balanced CR scheme by combining a reduction from [
Acknowledgements We thank Chandra Chekuri and Vasilis Livanos for useful
feedback, and for pointing out the connection with the work of [