An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization

Introduction and High-Level Details

We consider two notions in combinatorial optimization: a concrete problem (the classical $k$-median problem) and a formulation of new types of distributions (generalizations of dependent-rounding techniques); the breakthrough of Li & Svensson on the former uses special cases of the latter. We improve the approximation ratio of for the former, and develop efficient samplers for the latter – which, in particular, show that such distributions exist; we then combine the two to improve the run-time of our approximation algorithm for $k$-median. The ideas developed here also lead to optimal approximations for certain budgeted satisfiability problems, of which the classical budgeted set-cover problem is a special case. We discuss these contributions in further detail in Sections 1.1, 1.2, and 1.3.

Metric $k$-median is a fundamental location problem in combinatorial optimization. Herein, we are given a set $\mathcal{F}$ of facilities, a set $\mathcal{J}$ of clients, a budget $k$, and a symmetric distance-metric $d$ on $\mathcal{F}\cup\mathcal{J}$. The goal is to open a subset of at most $k$ facilities in $\mathcal{F}$ such that the total distance (or connection cost) from each client to its closest opened facility is minimized. Note that the only decision is which subset of the facilities to open. This problem is known to be $NP$-hard, so there has been much work done on designing approximations with provable performance guarantees; indeed, virtually every major technique in approximation algorithms has been used and/or developed for this problem and its variants.

Convex combinations of two integral solutions, with the corresponding convex combination of the number of open facilities being $k$, will be particularly useful for us:

(Bi-point solution) Given a $k$-median instance $\mathcal{I}$, a bi-point solution is a pair $\mathcal{F}_{1},\mathcal{F}_{2}\subseteq\mathcal{F}$ such that $|\mathcal{F}_{1}|\leq k\leq|\mathcal{F}_{2}|$, along with reals $a,b\geq 0$ with $a+b=1$ such that $a|\mathcal{F}_{1}|+b|\mathcal{F}_{2}|=k$. (That is, the convex combination of the two “solutions” is feasible for the natural LP relaxation of $\mathcal{I}$.) The cost of this bi-point solution is defined as $aD_{1}+bD_{2}$, where $D_{1}$ and $D_{2}$ are the connection costs of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ respectively.

Charikar, Guha, Tardos, and Shmoys used LP-rounding to achieve the first constant factor approximation ratio of $6\frac{2}{3}$ . Then, Jain and Vazirani applied Lagrangian Relaxation to remove the hard constraint of opening at most $k$ facilities, effectively reducing the problem to an easier version known as the Uncapacitated Facility Location (UFL) problem. Using this technique together with primal-dual methods for UFL, they first find a bi-point solution, losing a factor of 3. They then round this bi-point solution to an integral feasible solution losing another multiplicative factor of 2, yielding a $6$-approximation. Later, Jain, Mahdian, and Saberi (JMS) improved the approximation ratio of constructing the bi-point solution to $2$, resulting in a $4$-approximation . Following this, a local-search-based $(3+\epsilon)$-approximation algorithm was developed by Arya et al. .

Recently, Li and Svensson’s breakthrough work gave a $(1+\sqrt{3}+\epsilon)$-approximation algorithm for $k$-median . To accomplish this, they defined an $\alpha$-pseudo-approximation algorithm to be one that is an $\alpha$-approximation which, however, opens $k+O(1)$ facilities, and showed – very surprisingly – how to use such an algorithm as a blackbox to construct a true $(\alpha+\epsilon)$-approximation algorithm. They then took advantage of this by giving a bi-point rounding algorithm which opens $k+O(1)$ facilities, but loses a factor of $\frac{1+\sqrt{3}}{2}+\epsilon$ instead of the previous 2. Together with the factor of 2 lost during the JMS bi-point construction algorithm, this yields the final approximation ratio. Letting $N$ denote the input-size, the runtime of is $N^{O(1/\epsilon^{2})}$.

In this paperIn the conferrence version we claimed that we can also improve the cost of the bi-point solution, which was not correct. More details you can find in Appendix H., we improve the bi-point rounding step to give an algorithm for $k$-median with improved approximation ratio and runtime. Section 3 presents an improved approximation for rounding bi-point solutions; we obtain $1.3371+\epsilon$ instead of $\frac{1+\sqrt{3}}{2}+\epsilon\sim 1.366+\epsilon$. Section 2 develops our dependent rounding technique, a specific application of which reduces the dependence of the run-time on $\epsilon$ from $N^{O(1/\epsilon^{2})}$ as in , to $N^{O((1/\epsilon)\log(1/\epsilon))}$.

How can we round a bi-point solution to a feasible one? We present a rounding algorithm that obtains a factor of $1.3371+\epsilon$. This yields a $2\times 1.3371+\epsilon\sim(2.675+\epsilon)$-approximation algorithm for $k$-median, an improvement over Li and Svensson’s $(2.733+\epsilon)$. We analyze the worst-case instances of Li and Svensson’s approach, the structure of which leads us to the new algorithm.

Let the given bi-point solution be parametrized by $\mathcal{F}_{1},\mathcal{F}_{2},a,b,D_{1},$ and $D_{2}$ as in Definition 1.1. As an initial goal (which we will relax shortly), suppose we are interested in an algorithm which rounds this bi-point solution to an integer solution of cost at most $\alpha(aD_{1}+bD_{2})$, for some $\alpha$. As already mentioned, such an algorithm can be used to get a $(2\times\alpha)$-approximation to $k$-median. Suppose a client $j$ is closest to $i_{1}$ in solution $\mathcal{F}_{1}$, and $i_{2}$ in pseudo-solutionOne that may open more than $k$ facilities. $\mathcal{F}_{2}$. Ideally, one would like to round the bi-point solution in such a way that $i_{1}$ is open with probability $a$, and $i_{2}$ is open with the remaining probability $b$. Then the expected connection cost of $j$ would be exactly its contribution to the bi-point cost, and we would get a bi-point rounding factor of $1$. The problem is that we cannot directly correlate this pair of events for every single client, while still opening only $k$ facilities. Jain and Vazirani’s approach is to pair each $i_{1}\in\mathcal{F}_{1}$ with its closest neighbor in $\mathcal{F}_{2}$, and ensure that one of the two is open . This approach loses at most a factor of $2$, which is equal to the integrality gap of the $k$-median LP, and so is the best one might expect. However, Li and Svensson beat this factor by allowing their algorithm to open $k+c$ facilities. They then give a (surprising) method to convert such an algorithm to one that satisfies the budget-$k$ constraint, adding $\epsilon$ to the approximation constant, and a factor of $n^{O(c/\epsilon)}$ to the runtime. This method actually runs the algorithm on a polynomial number of sub-instances of the original problem, and thus is not limited by the integrality gap of the original LP. Thus we obtain our relaxed goal:

(Relaxed goal) Given a bi-point solution parametrized by $\mathcal{F}_{1},\mathcal{F}_{2},a,b,D_{1},$ and $D_{2}$ as in Definition 1.1, round it to an integer pseudo-solution using at most $k+f(\epsilon)$ facilities, and of cost at most $\alpha(aD_{1}+bD_{2})$ for $\alpha\sim 1.3371$. Here, $\epsilon>0$ is an arbitrary constant.

We will mainly discuss how to achieve such an improved $\alpha$ now, and defer discussion of the function $f$ to Section 1.2.1.

Li and Svensson’s approach, which we will generalize, is to create a cluster for every facility in $\mathcal{F}_{1}$, and put each facility in $\mathcal{F}_{2}$ into its nearest cluster. We refer to each cluster as a star. Each star has a single center in $\mathcal{F}_{1}$, and zero or more leaves in $\mathcal{F}_{2}$. It is useful to consider algorithms with the property that each star has either its center or all of its leaves opened (we will do better by relaxing this property). Then our client $j$ may always connect to either $i_{2}$, or the center of the star containing $i_{2}$, which cannot be too far away. The work of presents two such algorithms. The first is based on a knapsack-type LP, and yields a rounding factor of $1.53$ by opening two extra facilities. The second opens $a$ and $b$ fractions of $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ at random and obtains $\frac{1+\sqrt{3}+\epsilon}{2}\approx 1.366+\epsilon$ by opening $O(1/(ab\epsilon))$ extra facilities. (The former and the trivial solution $\mathcal{F}_{1}$ are used to handle the cases where $a$ or $b$ is close to zero.)

We improve this by first considering the stars with only one leaf (or 1-stars) separately from the stars with two or more leaves (or 2-stars). This allows us more freedom in shifting probability mass. For 1-stars, we do not need to worry about opening $a$ of the centers and $b$ of the leaves. We can instead consider either opening the leaf, or opening the center, and then choose the better of the two. For 2-stars, we still have the option of opening the center and leaves in proportion $a$ and $b$ respectively. However we also may shift the mass toward the centers, and open them in proportion $1$ and $b/2$ instead. This gives 4 possible combinations; we may try them all and take the best solution. When combined with the aforementioned knapsack-based algorithm, this idea improves the approximation from $1.53$ to $1.4$, with the same $n^{O(1/\epsilon)}$ runtime. However, it does not immediately improve the $(1+\sqrt{3})/2$ factor. It does, however, impose some useful structure on the distribution of clients in a worst-case instance. Also, we may consider shifting mass from 2-stars to 1-stars, the extreme being that we open the centers of all the 2-stars and open the remaining facilities in 1-stars. This must beat the (tight) bound of $D_{1}$, which would mean it does better than $(1+\sqrt{3})/2$. However, this effect is negligible if the number of 1-stars dominates the number of 2-stars. Thus, a worst-case instance must have a very large fraction of 1-stars.

But if there are so many 1-stars, perhaps we could close entirely (center and leaf) a tiny fraction of them and shift the mass to other stars. In fact, one may show a bi-point solution where 1.366 is the best we can do while still preserving the center-or-leaves property for all stars, but once we are allowed to close the center and leaf of some of the 1-stars, we get a factor of 1. This motivates the following strategy: For each 1-star, classify it as “long” or “short” based on its relative “size” (distance from the center to the leaf) compared to its distance to the nearest leaf of a 2-star. If many such stars are long, we may close both the center and the leaf, and still get a reasonable cost bound for any client connected to that star. This gives us the ability to consider shifting mass from these long stars to other stars. On the other hand, if many such stars are short, this actually means we may obtain a better cost bound for clients connected to centers of short 1-stars and leaves of 2-stars, by connecting them to the leaf of the short star in the worst case. (The worst-case structure mentioned above enforces that there are such clients.) In either case we obtain a factor strictly smaller than $(1+\sqrt{3})/2$.

To find the approximation constant of this new algorithm, we construct a factor-revealing non-linear program, the solution to which describes the new worst-case instance. The program is not convex, so local-search methods have no guarantee of finding the global optimum. However, there are 4 variables that, when fixed, render the system linear. Inspired by Zwick’s use of interval arithmetic , we consider a relaxation of the LP over a small interval of those 4 variables. The relaxation itself is linear and may be solved efficiently, but still gives a valid upper bound on the value of the original program in that interval. By splitting the search space into sufficiently small intervals, we are able to systematically prove an upper bound over the entire space, leading rigorously to the value of 1.3371.

Our approach shows there is potential to improve the approximation by improving the bi-point rounding algorithm. On the other hand, we give a family of explicit instances and bi-point solutions whose optimal rounding loses a factor of $\frac{1+\sqrt{2}}{2}\approx 1.207$, even when we allow $k+o(k)$ facilities to be opened.

2 Dependent rounding with almost-independence on small subsets

Dependent rounding has emerged as a useful technique for rounding-based algorithms. We start by discussing an “unweighted” special case of it, which captures much of its essence. Section 1.2.1 then discusses the general weighted case and its applications to $k$-median: specifically, our improvement of the function $f(\epsilon)$ of Definition 1.2 from the $\Theta(1/\epsilon)$ of to $\Theta(\log(1/\epsilon))$. This leads to our improved run-time.

Let us discuss the basic “unweighted” setting of dependent rounding. Starting with the key deterministic “pipage rounding” algorithm of Ageev & Sviridenko , dependent-rounding schemes have been interpreted probabilistically, and have found several applications and generalizations in combinatorial optimization (see, e.g., for a small sample). These naturally induce certain types of negative correlation and sometimes even-more powerful negative-association properties , which are useful in proving Chernoff-like concentration bounds on various monotone functions of such random variables. We consider settings where some form of positive correlation is desirable in dependent rounding, and construct efficiently-sampleable distributions that offer much more than what regular dependent-rounding and limited positive correlation ask for.

the “right” marginals: $\forall i$, $\Pr[X_{i}=1]=p_{i}$;

negative correlation: $\forall S\subseteq[n]~{}\forall b\in\{0,1\},~{}\Pr[\bigwedge_{i\in S}(X_{i}=b)]\leq\prod_{i\in S}\Pr[X_{i}=b]$.

As we see below, some algorithms for applications including $k$-median and budgeted MAX-SAT ask for the above properties, but also desire some form of positive correlation among selected (often “small”) subsets of the variables. Generalizing all of these, our basic problem is:

we want for some $t$ and suitably-small $\beta_{1},\beta_{2}$ that

Our results for the basic problem. We present a randomized linear time algorithm to sample $(X_{1},X_{2},\ldots,X_{n})\in\{0,1\}^{n}$ such that (A1), (A2) and (A3) hold, and with (A4) true with the following parameters:

In particular, for $t=o(\alpha\sqrt{n})$, we get $\beta_{1},\beta_{2}=o(1)$ – i.e., we have near-independence to within $(1\pm o(1))$ factors. This result is presented in Theorem 2.10. We add an extra element of randomness to the approach of , in order to obtain our results. (For applications where $\alpha$ or its substitutes $\hat{\alpha}$ and $\hat{q}$ are extremely close to zero, one can often round the $p_{j}$’s that are very close to or $1$ separately – e.g., by techniques such as those of Appendix G.)

In Section 2, we develop a general solution to the weighted dependent-rounding problem, which in particular solves the unweighted problem ((A1) – (A4)); this is done without assuming that $t=O(1)$, or that all the $p_{i}$’s are the same, etc. Since (A4) – for the weighted and unweighted cases – goes far beyond negative correlation (property (A3)) alone, we believe that our method could have a range of consequences, given the number of applications of dependent rounding seen over the last $15$ years. In any case, when specialized to the $k$-median application, this enables us to set $f(\epsilon)=\Theta(\log(1/\epsilon))$ in the context of Definition 1.2, and hence our overall run-time for $k$-median becomes $N^{O((1/\epsilon)\log(1/\epsilon))}$.

3 Budgeted MAX-SAT

The budgeted version of set-cover is well-understood: given a set-cover instance in which we can choose at most $k$ sets, we aim to make this choice in order to maximize the (weighted) number of ground-set elements covered . The work of presents an $(1-1/e)$-approximation for this problem, and shows the hardness of obtaining an $(1-1/e+\epsilon)$-approximation. This problem can be naturally generalized as follows. Consider an arbitrary CNF-SAT formula $\phi$ over Boolean variables $x_{1},x_{2},\ldots,x_{n}$, and with weight $w_{i}\geq 0$ for clause $i$. We aim to assign a True/False value to each $x_{j}$, in order to maximize the total weight of the satisfied clauses. However, we also have a hard budget-constraint as follows. The cost model is that there exist $a,b\geq 0$ such that for each $x_{j}$, we pay $a$ if we set $x_{j}$ to True, and $b$ if we set $x_{j}$ to False. We have a hard budget of $B$ on our total cost. (Such a budget-constraint is perhaps more well-motivated when we view each variable as having two possible general choices, rather than True/False.) Thus, letting $X_{j}$ be the indicator variable for $x_{j}$ being true, our budget constraint for the case $a\geq b$ is that $\sum_{j}X_{j}\leq k^{\prime}$ (where $k^{\prime}=\lfloor(B-nb)/(a-b)\rfloor$); if $b>a$, then by complementing all variables, we get a constraint of the same type. Thus, we may assume w.l.o.g. that $\sum_{j}X_{j}\leq k$ is our budget constraint, for some given integer $k$. Note that budgeted set-cover is the special case of this problem when the formula $\phi$ has no variables negated. The constraint “$\sum_{j}X_{j}\leq k$” naturally suggests dependent rounding; on the other hand, clauses in $\phi$ such as “$x_{i}\vee\overline{x_{j}}$” would benefit from positive correlation. For this budgeted MAX-SAT problem, though, some of our rounding approaches for $k$-median show that the structure of the problem allows for a simple rounding solution, leading to an essentially-best-possible $(1-1/e-\epsilon)$-approximation for any constant $\epsilon>0$. Please see Appendix G.

4 Perspective

Our first contribution is an in-depth analysis of the bi-point rounding algorithm of , and observe that their rounding can be improved by a multi-pronged approach. In essence, these different “prongs” have different worst-case scenarios, and hence a suitable combination of them can do better with any adversarial strategy for choosing the input instance to the problem. This leads to an improved approximation ratio for the fundamental $k$-median problem.

Our second major contribution is to (weighted) dependent rounding. This general technique has seen numerous applications over the last $15$ years or so, primarily since it can handle hard constraints such as (A2), and can also guarantee negative correlation (A3), which is useful for concentration bounds and other applications. However, the existing body of work largely does not address positive correlation, let alone near-independence, even for relatively-small subsets of the underlying variables $X_{i}$. We are able to show that we can guarantee all the existing properties of dependent rounding, and guarantee near-independence for not-too-large subsets, in the sense of (A4). We believe that this will yield further applications. Our dependent-rounding approach also helps improve the run-time of the $k$-median application.

Dependent rounding with near-independence on small subsets

“almost-integrality”: all but at most one of the $X_{i}$ lies in $\{0,1\}$ (with the remaining at most one element lying in $$);

$\Pr[\sum_{i}a_{i}X_{i}=\sum_{i}a_{i}p_{i}]=1$;

$\forall S\subseteq[n]$, $\text{\bf E}[\prod_{i\in S}(1-X_{i})]\leq\prod_{i\in S}(1-p_{i})$, and $\text{\bf E}[\prod_{i\in S}X_{i}]\leq\prod_{i\in S}p_{i}$;

if the weights $a_{i}$ are “not too far apart”, there is near-independence for subsets of $\{X_{1},X_{2},\ldots,X_{n}\}$ that are of cardinality at most $t$, analogously to (A4).

In this section we will give an $O(n)$-time algorithm (called DepRound) for sampling from such a distribution; see Section 2.2. In particular, this shows that such distributions exist. This algorithm is a generalization of the unweighted version given in , with a specific (random) ordering of operations, leading to the added property (A4’) of near-independence. Our main theorem is Theorem 2.10. It basically says, in the notation of (2), that we can achieve $\beta_{1},\beta_{2}=O(t^{2}/(n\alpha^{3}))$ when $t\leq O(\sqrt{n\alpha^{3}})$. Thus, we obtain near-independence up to fairly large sizes $t$. This bound is further improved in Section 2.4. Let us also remark about the possible (sole) index $i$ that is left unrounded, as in (A0’). Three simple ways to round this are to round down, round up, or round randomly; these can be chosen in a problem-specific manner. None of these three fits the $k$-median application perfectly; a different probabilistic handling of this index $i$ is done in Section 3.3.

Note that DepRound could be described more simply as a form of pipage rounding (with an added, crucial, element of processing the variables in random order), with flow adjusted proportionally to the weights. However, in order to facilitate the analysis of (A4’), we give the following, less compact description of the algorithm. Also note that we will apply this method to $k$-median in Section 3.3, but here it is described as a general-purpose rounding procedure, independent of $k$-median; this is because we believe that this method is of independent interest since it goes much beyond negative correlation. Thus, the reader is asked to note that the notation defined in this section is largely separate from that of the other sections.

$\gamma_{1},\gamma_{2}\in$, and at least one of the two variables is integral (0 or 1);

$\text{\bf E}[\gamma_{1}]=\beta_{1}$ and $\text{\bf E}[\gamma_{2}]=\beta_{2}$;

$\Pr\left[a_{1}\gamma_{1}+a_{2}\gamma_{2}=a_{1}\beta_{1}+a_{2}\beta_{2}\right]=1$; and

$\text{\bf E}[\gamma_{1}\gamma_{2}]\leq\beta_{1}\beta_{2}$, and $\text{\bf E}[(1-\gamma_{1})(1-\gamma_{2})\leq(1-\beta_{1})(1-\beta_{2})$.

Now define $\text{\sc simplify}(a_{1},a_{2},\beta_{1},\beta_{2})$ as follows. There are four cases:

$0\leq a_{1}\beta_{1}+a_{2}\beta_{2}\leq\min\{a_{1},a_{2}\}$. With probability $a_{2}\beta_{2}/(a_{1}\beta_{1}+a_{2}\beta_{2})$ set $\gamma_{1}=0$. With remaining probability set $\gamma_{2}=0$.

$a_{1}<a_{1}\beta_{1}+a_{2}\beta_{2}<a_{2}$. With probability $\beta_{1}$ set $\gamma_{1}=1$. With remaining probability set $\gamma_{1}=0$.

$a_{2}<a_{1}\beta_{1}+a_{2}\beta_{2}<a_{1}$. With probability $\beta_{2}$ set $\gamma_{2}=1$. With remaining probability set $\gamma_{2}=0$.

$\max\{a_{1},a_{2}\}\leq a_{1}\beta_{1}+a_{2}\beta_{2}\leq a_{1}+a_{2}$. With probability $a_{2}(1-\beta_{2})/(a_{1}(1-\beta_{1})+a_{2}(1-\beta_{2}))$ set $\gamma_{1}=1$. With remaining probability set $\gamma_{2}=1$.

If we set $\gamma_{1}=0$, then set $\gamma_{2}=\beta_{2}+\beta_{1}\frac{a_{1}}{a_{2}}$.

If we set $\gamma_{1}=1$, then set $\gamma_{2}=\beta_{2}-(1-\beta_{1})\frac{a_{1}}{a_{2}}$.

If we set $\gamma_{2}=0$, then set $\gamma_{1}=\beta_{1}+\beta_{2}\frac{a_{2}}{a_{1}}$.

If we set $\gamma_{2}=1$, then set $\gamma_{1}=\beta_{1}-(1-\beta_{2})\frac{a_{2}}{a_{1}}$.

$\textsc{Simplify}(a_{1},a_{2},\beta_{1},\beta_{2})$ outputs $(\gamma_{1},\gamma_{2})$ with properties (B0), (B1), (B2), and (B3).

This is straightforward to show; we provide a partial proof in Appendix A.

2 Main algorithm: DepRound

We now describe the full dependent rounding algorithm, which we denote DepRound.

Define $X^{(s)}=(X^{(s)}_{1},X^{(s)}_{2},\ldots,X^{(s)}_{n})$ to be the value of $X$ after the step $s$ of the rounding process, with $X^{(0)}=P$, and $X^{(T)}=X$ if the algorithm halts after $T$ steps. We say $X_{i}$ is fixed during step $s$ if $X_{i}^{(s-1)}$ is fractional but $X_{i}^{(s)}$ is integral, since this implies $X_{i}$ will not change in any future steps.

It is not hard to follow the proof of and validate properties (A0’), (A1’), (A2’), and (A3’); we present a proof sketch below.

DepRound samples a vector in $O(n)$ time; this vector satisfies properties (A0’), (A1’), (A2’), and (A3’).

By definition, DepRound ends only when there is at most one fractional variable remaining, and by definition of Simplify, the remaining variables are either 0 or 1, showing (A0’). Since at least one variable is fixed in each constant-time step, the algorithm takes at most $n-1$ steps, and thus runs in linear time. (The random permutation $\pi$ may also be generated in linear time.)

(B1) implies that for each $i$ and $s$, $\text{\bf E}[X_{i}^{(s)}]=X_{i}^{(s-1)}$. By induction, this implies (A1’). (B2) implies that $\sum_{i}a_{i}X^{(T)}_{i}=\sum_{i}a_{i}X^{(T-1)}_{i}=\ldots=\sum_{i}a_{i}X^{(0)}=\sum_{i}a_{i}p_{i}$, thus implying (A2’). Finally, let $X_{i}$ and $X_{j}$ be the variables chosen in line 4 during step $t$. If $i,j\in S$, then (B3) implies $\text{\bf E}[\prod_{i\in S}X^{(s)}_{i}]\leq\prod_{i\in S}X^{(s-1)}_{i}$ and $\text{\bf E}[\prod_{i\in S}(1-X^{(s)}_{i})]\leq\prod_{i\in S}(1-X^{(s-1)}_{i})$ (all other terms in the product are constant). If only one or neither of $i,j$ are in $S$, then the same hold with equality. By induction, these imply (A3’). ∎

Note that the above properties hold under any ordering $\pi$. The additional element of using $\pi$ to process the indices in random order is needed only for the new property (A4’).

3 Limited dependence

In this section we will prove the limited dependence property (A4’). Consider a subset $I\subseteq[n]$ of $t$ indices, with corresponding “target” bits $(b_{i})_{i\in I}\in\{0,1\}^{t}$. For each $i\in I$, define $Y_{i}:=X_{i}$ if $b_{i}=1$, or $Y_{i}:=1-X_{i}$ if $b_{i}=0$. We are interested in the value of $\text{\bf E}\left[\prod_{i\in I}Y_{i}\right]$, which is essentially equal to the joint probability $\bigwedge_{i\in I}(X_{i}=b_{i})$. Note these are not exactly equivalent, because of the one fractional variable. This variable must be handled in a domain-specific way to ensure this property holds, as we will do when applying it to $k$-median.

From property (A1’), we have $\text{\bf E}[X_{i}]=p_{i}$. Similarly, $\forall i\in I$, define $q_{i}$ such that $\text{\bf E}[Y_{i}]=q_{i}$. That is, let $q_{i}$ be either $p_{i}$ or $1-p_{i}$ if $b_{i}$ is 1 or 0, respectively. If we independently rounded each variable, $\text{\bf E}[\prod_{i\in I}Y_{i}]$ would be exactly $\prod_{i\in I}q_{i}$ (but (A2’) would be violated). We will show that when set $I$ is not too large, the product is still very close to $\prod_{i\in I}q_{i}$ in expectation (i.e., that the variables $\{X_{i}\}_{i\in I}$ are near-independent).

During a run of DepRound, we say that two variables $X_{i}$ and $X_{j}$ are co-rounded if they are both changed in the same step. We will first show that if two variables are far apart in $\pi(X)$, then they are unlikely to be co-rounded. Then we will show that a group of variables is near-independent if the probability of any two of them being co-rounded is small. Finally, we will show that for a small enough set $I$ variables are very likely to be far apart, and thus very likely to remain independent.

Recall that DepRound always calls Simplify on the two left-most fractional variables in $\pi(X)$, fixing at least one of them (to 0 or 1). Thus, once a variable survives (i.e., remains fractional after) one step it will continue to be included in all subsequent Simplify steps until it gets fixed (or becomes the last remaining fractional variable). We want to upper bound the probability that a variable survives for too long. We first show that in any two consecutive steps involving $X_{i}$, there is a minimum probability that $X_{i}$ gets fixed (if the weights are not too different).

Let $a_{min}:=\min_{i}\{a_{i}\}$ and $a_{max}:=\max_{i}\{a_{i}\}$ be the minimum and maximum weights. Suppose $\frac{a_{max}}{a_{min}}\leq 2$. Suppose $X_{i}$ is co-rounded with variable $X_{j}$ in step $s$, and if it survives it will be co-rounded with variable $X_{k}$ in step $s+1$. Let $\beta_{j}:=X_{j}^{(s-1)}$ and $\beta_{k}:=X_{k}^{(s)}$. Then $X_{i}$ will be fixed in one of these two steps with probability at least $p=\min\{\beta_{j},1-\beta_{j}\}\cdot\min\{\beta_{k},1-\beta_{k}\}$.

What is the probability that $X_{i}$ is fixed in the first step? It depends on which of the four cases occur. In case I, it is $\frac{a_{j}\beta_{j}}{a_{i}\beta_{i}+a_{j}\beta_{j}}\geq\frac{a_{j}\beta_{j}}{a_{j}}=\beta_{j}$. In case II it is 1. In case IV it is $\frac{a_{j}(1-\beta_{j})}{a_{i}(1-\beta_{i})+a_{j}(1-\beta_{j})}=\frac{a_{j}(1-\beta_{j})}{a_{i}+a_{j}-(a_{i}\beta_{i}+a_{j}\beta_{j})}\geq\frac{a_{j}(1-\beta_{j})}{a_{i}+a_{j}-a_{i}}=1-\beta_{j}$. In these three cases, $X_{i}$ is fixed with probability at least $\min\{\beta_{j},1-\beta_{j}\}\geq p$. However, in the remaining case III, $X_{i}$ will be fixed with probability 0.

Given that case III occurs in the first step, what is the probability that $X_{i}$ gets fixed in the second step? It is at least the probability that one of cases I, II or IV occur in the second step, times $\min\{\beta_{k},1-\beta_{k}\}$ (by the same reasoning as above). When case III occurs in the first step, $X_{i}^{(s)}$ gets set randomly to one of two values: $\beta_{i}+\beta_{j}\frac{a_{j}}{a_{i}}$ or $\beta_{i}-(1-\beta_{j})\frac{a_{j}}{a_{i}}$, with probability $1-\beta_{j}$ or $\beta_{j}$, respectively. These values differ by exactly $\frac{a_{j}}{a_{i}}\geq\frac{a_{min}}{a_{max}}\geq\frac{1}{2}$. Now, in the second step, case III only occurs if $X_{i}^{(s)}$ lies in the open interval $(\frac{a_{k}}{a_{i}}-\frac{a_{k}}{a_{i}}\beta_{k},1-\frac{a_{k}}{a_{i}}\beta_{k})$. But the distance between any two numbers in this interval is strictly less than $1-\frac{a_{k}}{a_{i}}\leq 1-\frac{a_{min}}{a_{max}}\leq\frac{1}{2}$. Therefore, the two possible values of $X_{i}^{(s)}$ cannot both lie in the interval required for case III, so with probability at least $\min\{\beta_{j},1-\beta_{j}\}$, the second step will be a case other than III. ∎

Important remark on notation: In the following paragraph, by overloading notation, we fix the random permutation $\pi$ to be some arbitrary but fixed $\pi$. Several pieces of notation such as $\sigma,J_{i}$, and, most importantly, $\delta_{k}:=\prod_{i=0}^{\lfloor|J_{k}|/2\rfloor}(1-\alpha_{j_{k,2i}}\alpha_{j_{k,2i+1}})$, are functions of this $\pi$. All statements and proofs until the end of the proof of Lemma 2.5, are conditional on the random permutation equaling $\pi$ (this is sometimes stated explicitly, sometimes not).

Lemma 2.3 implies that the probability of a variable’s survival decays exponentially with the number of steps survived. Now, given a permutation $\pi\in S_{n}$, let $\sigma:[t]\to I$ be the bijection such that $\pi^{-1}(\sigma(1))<\pi^{-1}(\sigma(2))<\cdots<\pi^{-1}(\sigma(t))$. Let

be the set of the indices not in $I$. Now partition $J$ into sequences $(J_{0},J_{1},\ldots,J_{t})$, using elements of $I$ as dividers. Formally, for $k=0,\ldots,t$, let $J_{k}$ be the maximal sequence $(j_{k,1},j_{k,2},\ldots)$ satisfying $\pi^{-1}(\sigma(k))<\pi^{-1}(j_{k,1})<\pi^{-1}(j_{k,2})<\cdots<\pi^{-1}(\sigma(k+1))$, letting $\pi^{-1}(\sigma(0)):=0$ and $\pi^{-1}(\sigma(i+1)):=n+1$. Note that if $\sigma(k)$ and $\sigma(k+1)$ are directly adjacent in $\pi$, then $J_{k}$ will be empty, as seen in the example below.

For $k\in[t-1]$, let $Z_{k}$ be the “bad” event that DepRound co-rounds $X_{\sigma(k)}$ and $X_{\sigma(k+1)}$. For $Z_{k}$ to occur, it is necessary that $X_{\sigma(k)}$ be co-rounded with all variables inbetween as well. For example, in the above sequence, $Z_{1}$ means that $X_{\sigma(1)}=X_{3}$ must be co-rounded with $X_{4},X_{1},X_{9},X_{6}$, (surviving each round), and finally $X_{8}$. The next lemma bounds $\Pr[Z_{k}]$ in terms of the set $J_{k}$.

Let $\alpha_{i}:=\min\{p_{i},1-p_{i}\}$. If $\frac{a_{max}}{a_{min}}\leq 2$, then $\forall k\in[t-1]$, we have $\Pr[Z_{k}]\leq\delta_{k}$, where $\delta_{k}:=\prod_{i=1}^{\lfloor|J_{k}|/2\rfloor}(1-\alpha_{j_{k,2i-1}}\alpha_{j_{k,2i}})$.

3.2 Seldom co-rounded variables are near-independent

The following lemmas show that if the probability of variables in $\{X_{i}\}_{i\in I}$ being co-rounded is low, then $\text{\bf E}[\prod_{i\in I}Y_{i}]\approx\prod_{i\in I}q_{i}$. For notational convenience, define $\delta_{t}:=0$.

Let $I_{k}:=\{\sigma(k),\sigma(k+1),\ldots,\sigma(t)\}$. Let $\mathcal{E}_{k}$ denote a set of events which consists of exactly one of $Z_{i}$ or $(\bar{Z}_{i}\land Y_{\sigma(i)}=y_{i})$ for each $i=1\ldots k$, where $y_{i}$ is some attainable value of $Y_{\sigma(i)}$. Then, conditioned on a fixed permutation $\pi$, the following holds for all $k\in[t]$:

Recall $\pi\in S_{n}$ is a fixed permutation; all probabilities and expectations in this proof are conditioned on $\pi$. This proof formalizes the idea that if $Z_{k}$ doesn’t occur, then $X_{\sigma(k)}$ and $X_{\sigma(k+1)}$ remain independent. If it does occur, the effect on the expected value is limited by $\delta_{k}$.

After step $s$ of DepRound, we may consider the remainder of the algorithm as simply a recursive call on vector $X^{(s)}$ (using the same permutation $\pi$). Let $D_{k}$ be the first such call where $X_{\sigma(k)}$ is one of the two left-most fractional variables to be co-rounded. Then there is at most one fractional variable to the left of $X_{\sigma(k)}$, say $X_{i_{0}}$, and all variables to the right still have their initial values from $P$.

The key observation is that while events in $\mathcal{E}_{k-1}$ do affect the identity and initial value of $X_{i_{0}}$, they do not further influence the outcome of $D_{k}$. The only way $D_{k}$ could be further influenced is if $\mathcal{E}_{k-1}$ contains the event $Y_{\sigma(j)}=y_{j}$, where $X_{i_{0}}$ is with some probability the variable $X_{\sigma(j)}$. However, for each $j=1\ldots k-1$, $\mathcal{E}_{k-1}$ either contains $\bar{Z}_{j}$ (which means $X_{\sigma(j)}$ was fixed earlier and cannot be $X_{i_{0}}$), or it lacks $Y_{\sigma(j)}=y_{j}$.

This means that all the properties of DepRound shown so far (which hold for a fixed $\pi$) still hold for $D_{k}$ when conditioned on $\mathcal{E}_{k-1}$. Namely, we have $E[X_{i}\mid\mathcal{E}_{k-1}]=p_{i}$ (for all $X_{i}$ to the right of and including $X_{\sigma(k)}$), $\Pr[Z_{k}|\mathcal{E}_{k-1}]\leq\delta_{k}$, and – as we will claim by induction – (5) for $I_{k}$. The bounds derived below handle the problematic compound event $Z_{k}\land Y_{\sigma(k)}=y_{k}$ explicitly by assuming that when $Z_{k}$ occurs, $Y_{\sigma(k)}$ always attains its worst-case value (1 for the upper bound, or 0 for the lower bound).

As a base case, consider the singleton set $I_{t}=\{\sigma(t)\}$. As just described, we have $\text{\bf E}[X_{\sigma(t)}\mid\mathcal{E}_{k-1}]=p_{\sigma(t)}$ , so $\text{\bf E}[Y_{\sigma(t)}\mid\mathcal{E}_{k-1}]=q_{\sigma(t)}$, and (5) follows from $\delta_{t}=0$. We now proceed by induction on $k$, counting backward from $t$. Let $W_{k}:=\prod_{i\in{I_{k}}}Y_{i}=\prod_{j=k}^{t}Y_{\sigma(j)}$. Let $\bar{Z}_{k}$ be the complement of event $Z_{k}$. For some $k<t$, assume that (5) holds for $D_{k+1}$ with set $I_{k+1}$. Then, using the independence properties just mentioned, we have that $\text{\bf E}[W_{k}\mid\mathcal{E}_{k-1}]$ is

Similarly, we have that $\text{\bf E}[W_{k}\mid\mathcal{E}_{k-1}]$ is

But also $\text{\bf E}[W_{k}|\mathcal{E}_{k-1}]\geq 0\cdot\prod_{i\in I_{k+1}}(q_{i}-\delta_{\sigma^{-1}(i)})$ so we use the better of the two lower bounds. ∎

Remark. From now on, we will no longer take $\pi$ as fixed, and hence the $\delta_{k}$ (which are functions of the random permutation) will be viewed as random variables.

If $\frac{a_{max}}{a_{min}}\leq 2$, we have

Apply Lemma 2.5 with $k=1$ and $\mathcal{E}=\emptyset$. Recall $\delta_{t}:=0$. Take the expectation over all permutations $\pi$, and then factor out the constant $\prod_{i\in I}q_{i}$. ∎

3.3 Small subsets are spread out

The following lemma gives a very useful combinatorial characterization of the distribution of $\{J_{k}\}$.

Let $g=(g_{1},\dots,g_{t+1})$ be a sequence of nonnegative integers which sum to $n-t$, picked uniformly at random from all such possible sequences. Then the distribution of $g$ is equal to the distribution of $(|J_{0}|,\dots,|J_{t}|)$. Both distributions are symmetric.

Consider the mapping $\Phi_{I}:S_{n}\to\{0,1\}^{n}$ from permutations on $[n]$ to binary strings of length $n$, in which we replace each index in $I$ with a 1, and the rest with a 0. Also define $\Theta$ to be the following standard combinatorial bijection from binary strings to arrangements of balls in boxes: given a binary string $s$, first add a 1 to the beginning and end of the string; then, viewing the space between each nearest pair of 1’s as a ‘box’, and the zeros between each pair as ‘balls’ in that box, let $\Theta(s)$ be the sequence which counts the number of balls in each box, from left to right. For an arbitrary permutation $\pi$, and the corresponding sets $\{J_{k}\}$, we see that $|J_{k}|$ corresponds to the number of zeros between the $k$’th and the $(k+1)$’th 1 in $\Phi_{I}(\pi)$, and thus to the number of balls in the corresponding box in $(\Theta\circ\Phi_{I})(\pi)$. Therefore we have that $(\Theta\circ\Phi_{I})(\pi)=(|J_{0}|,\ldots,|J_{t}|)$.

Now recall that DepRound chooses a uniformly random permutation $\pi\in S_{n}$. Notice that $\Phi_{I}(\pi)$ only maps to binary strings of length $n$ with exactly $|I|=t$ ones. Furthermore, for each such binary string, there are exactly $t!(n-t)!$ permutations which map to it. Thus, $\Phi_{I}(\pi)$ is uniformly distributed over all $\binom{n}{t}$ such binary strings. $\Theta$ provides an exact bijection between binary strings of length $n$ with $t$ ones, and sequences $g$ as defined in the lemma. This implies that $(\Theta\circ\Phi_{I})(\pi)$ – and thus $(|J_{0}|,\ldots,|J_{t}|)$ – is uniformly distributed over all such possible sequences $g$.

Furthermore, by definition of $g$, all permutations of a sequence $g$ would be equally likely. Therefore the distribution of $g$, and thus $(|J_{0}|,\ldots,|J_{t}|)$, is symmetric. ∎

Remark. Note that the above distribution over balls-in-boxes is such that each possible arrangement is equally likely. This is not to be confused with distributions obtained by randomly and independently throwing the balls into the boxes.

Consider a subset $C\subseteq[t]$ of size $c$, and let $J_{C}:=\bigcup_{k\in C}J_{k}$. Then for any constant $0<x<1$,

From Lemma 2.7 the distribution of $(|J_{0}|,|J_{1}|,\ldots|J_{t}|)$ is symmetric. Thus, when considering the distribution of a function of the sizes $\{|J_{k}|\}_{k\in C}$, we may w.l.o.g. assume that $J_{C}=J_{0}\cup J_{1}\cup\ldots\cup J_{c-1}$. Notice since $\{J_{k}\}$ are all disjoint, we have $|J_{C}|=\sum_{k\in C}|J_{k}|$; also, $|J_{C}|\leq|J|=n-t$.

Now for a quick exercise in counting. From the previous proof, $\Phi_{I}(\pi)$ maps permutations uniformly to $n$-digit binary strings with $t$ 1’s. For a given permutation $\pi$, we observe that $\sum_{k=0}^{c-1}|J_{k}|=m$ iff the binary string $\Phi_{I}(\pi)$ has exactly $m$ zeros before the $c$’th 1 (i.e., there are $m$ total balls in the first $c$ boxes). How many of the $\binom{n}{t}$ possible strings have this property? It is the number of ways to put $(c-1)$ 1’s in the first $(m+c-1)$ digits, a $1$ in the $(m+c)$’th digit, and $(t-c)$ 1’s in the remaining $(n-m-c)$ digits. Thus,

where $n^{\underline{c}}:=n\cdot(n-1)\cdots(n-c+1)$ denotes the falling factorial. Now we combine (6) and (7), and relax the bound by allowing $m$ to go up to infinity. The resulting series converges when $0<x<1$.

A quick proof of the series’ convergence is to start with $\sum_{m=0}^{\infty}x^{m}=1/(1-x)$, and take the $(c-1)$’th derivative of both sides, with respect to $x$. ∎

Let $\delta_{k}:=\prod_{i=0}^{\lfloor|J_{k}|/2\rfloor}(1-\alpha_{j_{k,2i}}\alpha_{j_{k,2i+1}})$, and $\alpha:=\min_{j}\{\alpha_{j}\}$. Let $C\subseteq[t]$ of size $c$. If $\frac{a_{max}}{a_{min}}\leq 2$,

First, recall by definition that $q_{i}$ is either $p_{i}$ or $1-p_{i}$, so $q_{i}\geq\min\{p_{i},1-p_{i}\}=\alpha_{i}\geq\alpha$. Then

In the first line we used $\lfloor x/2\rfloor\geq(x-1)/2$. In (9) we used $\sqrt{1-x^{2}}\leq\sqrt{1-x^{2}+x^{4}/4}=1-x^{2}/2$. In (2.4) we applied Lemma 2.8 and then used $\alpha\leq 1/2$. ∎

Now we can complete the bound given in Lemma 2.6. The upper bound follows by expanding the binomial, bounding the expected value of each term, and then refactoring. The lower bound follows by the Weierstrass product inequality.

Thus we are led to our main theorem on dependent rounding (which in turn is improved upon, with further work, in Section 2.4):

Let $(X_{1},\ldots,X_{n})$ be the vector returned by running DepRound with probabilities $(p_{1},\ldots,\allowbreak p_{n})$ and positive weights $(a_{1},\ldots,a_{n})$. Let $I^{+}$ and $I^{-}$ be disjoint subsets of $[n]$. Define $\alpha:=\min_{i}\{p_{i},1-p_{i}\}$, $I:=I^{+}\cup I^{-}$, $t=|I|$, and $\lambda:=\displaystyle\prod_{i\in I^{+}}p_{i}\prod_{i\in I^{-}}(1-p_{i})$. Then if $\displaystyle\max_{i,j}\left\{\frac{a_{i}}{a_{j}}\right\}\leq 2$, we have

For all $i\in I^{+}$, set $b_{i}=1$; for all $i\in I^{-}$, set $b_{i}=0$. Then apply (11) and (12) to Lemma 2.6. The theorem follows by recognizing that

Note that $\left(1+\frac{16t}{7n\alpha^{3}}\right)^{t-1}\leq\exp\left(\frac{16t^{2}}{7n\alpha^{3}}\right)$. Thus we see that Theorem 2.10 allows us to bound the dependence among groups of variables as large as $O(\sqrt{n})$ when $\alpha=\Theta(1)$.

4 Improvements and Special Cases

In this section we present several refinements of Theorem 2.10. The proofs all follow the same outline as that of the main result; we describe only the places where they differ. We reuse the same definitions unless stated otherwise.

In our $k$-median application we will have that all $p_{i}$ are uniform. In this case, if the maximum ratio of weights is sufficiently small, we can tighten the bound to show a weaker dependency on $\alpha$.

Suppose $p_{1}=p_{2}=\cdots=p_{n}=p$ and $\alpha=\min\{p,1-p\}$. Then if $\frac{a_{max}}{a_{min}}\leq 1+\alpha$, we have

The improvement comes from strengthening the result of Lemma 2.3: Suppose $X_{i}$ is co-rounded with variable $X_{j}$ in step $s$ and then (if it survives) variable $X_{k}$ in step $s+1$, where $X_{j}^{(s-1)}=X_{k}^{(s)}=p$. Then we can show $X_{i}$ will be fixed in one of these two steps with probability at least $\alpha$.

First assume that during both steps Case III occurs. By requirements for Case III, we have $\frac{a_{j}}{a_{i}}(1-p)<X_{i}^{(s-1)}<1-\frac{a_{j}}{a_{i}}p$ and $\frac{a_{k}}{a_{i}}(1-p)<X_{i}^{(s)}<1-\frac{a_{k}}{a_{i}}p$. Suppose $X_{j}$ is fixed to 0 in step $s$. Then

In either outcome, we have a contradiction. Therefore in at least one of the two steps, a case other than III must occur. As shown in the proof of Lemma 2.3, in the other 3 cases $X_{i}$ will be fixed with probability at least $\min\{p,1-p\}=\alpha$.

This stronger bound carries through the remaining lemmas in a straightforward way. Following the proof for Lemma 2.4, starting from (4), we get

So Lemmas 2.4, 2.5 and 2.6 will now hold with the new definition $\delta_{k}:=(1-\alpha)^{\lfloor|J_{k}|/2\rfloor}$. Then in Lemma 2.9, we get

In the unweighted case (where all $a_{i}=1$), we can similarly tighten the bound. We can also refine the bound to be in terms of a sort of average of the probabilities instead of just the most extreme.

Let $\mathbf{X}:=(X_{1},\ldots,X_{n})$ be the vector returned by running DepRound with probabilities $(p_{1},\ldots,p_{n})$ and unit weights $(1,\ldots,1)$. Let $\alpha_{i}=\min\{p_{i},1-p_{i}\}$. Let $I^{+}$ and $I^{-}$ be disjoint subsets of $[n]$. Let $q_{i}=p_{i}$ for $i\in I^{+}$, and let $q_{i}=1-p_{i}$ for $i\in I^{-}$; let $I=I^{+}\cup I^{-}$. Define

Furthermore, if $\sum_{i}p_{i}$ is an integer, then $\mathbf{X}$ has no fractional elements.

Uniform weights allow us to strengthen Lemma 2.3 even further; in particular, we no longer need to consider pairs of steps. Suppose $X_{i}$ is co-rounded with $X_{j}$ during step $s$. Since all $a_{i}=1$, Cases II and III cannot occur. Thus, $X_{i}$ will be fixed with probability at least $\min\{X_{j}^{(s-1)},1-X_{j}^{(s-1)}\}=\alpha_{j}$ (as in proof of Lemma 2.3).