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)