The Dirichlet Mechanism for Rounding with Strong Negative Correlation, with Applications

Harris, David G.; Li, George Z.; Raju, Nitya; Valieva, Renata

doi:10.4230/LIPIcs.ICALP.2026.107

The Dirichlet Mechanism for Rounding with Strong Negative Correlation, with Applications

David G. Harris University of Maryland, College Park, MD, USA George Z. Li Carnegie Mellon University, Pittsburgh, PA, USA Nitya Raju University of Maryland, College Park, MD, USA Renata Valieva University of Maryland, College Park, MD, USA

Abstract

Many optimization and scheduling problems can be abstracted in terms of a bipartite “assignment graph” $G=(L\cup R,E)$ , where the goal is to select exactly one edge for each right-node. For example, a right-node may correspond to a job, and a left-node to a possible machine assignment. A common strategy to solve such problems is to obtain a fractional relaxation $x_{e}$ for each edge $e$ , and then have each right-node independently select an edge with probability $x_{e}$ . However, this may cause the left-nodes to become unevenly loaded, leading to suboptimal solutions for some problems.

To address this, a number of algorithms for dependent rounding with strong negative correlation have been developed, e.g. Bansal, Srinivasan & Svensson (2021), Im & Shadloo (2020), Im & Li (2023), Harris (2024), Naor, Srinivasan & Wajc (2025). We introduce a new method for this, which we call the Dirichlet mechanism. It is based on having each left-node draw Dirichlet random variables for its edges, and then having each right-node select an edge based on these values. This achieves quantitatively stronger negative correlation than previous algorithms, and is also simpler since it avoids the need for a tie-breaking mechanism.

We illustrate the mechanism with improved approximation ratios for two problems. For oblivious online dependent rounding, we achieve a $0.68$ -approximation which improves upon the previous $0.652$ -approximation of Naor, Srinivasan & Wajc (2025). For the problem of scheduling jobs on unrelated machines to minimize weighted completion time, we achieve a $1.387$ -approximation which improves upon the $1.398$ -approximation of Harris (2024). (A recent algorithm of Li (2025) based on iterated rounding also provides a $1.36$ -approximation if the weights of each job are independent of machine.)

Keywords and phrases:

Dirichlet distribution, copula, weighted completion time, online rounding

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Probabilistic algorithms ; Mathematics of computing

\rightarrow

Combinatorial optimization

Acknowledgements:

We thank Mark Jacobson for suggesting the use of a Dirichlet distribution, and for explaining its definitions and properties.

DOI:

10.4230/LIPIcs.ICALP.2026.107

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Many scheduling and resource allocation problems can be formulated as a bipartite assignment problem: we are given a complete bipartite graph $G=(U\cup V,E)$ , and we wish to select a set of edges $K$ which intersects each right-node $v\in V$ exactly once. That is, $K$ is a “half-matching”. For instance, $V$ can represent a set of jobs to be scheduled, and $U$ can represent a set of possible machines. Alternatively, $V$ can represent a set of items to be sold, and $U$ can represent potential buyers.

There is a natural strategy for solving such problems. First, one solves a relaxation (e.g., an LP relaxation) to obtain a fractional solution $(x_{e}:e\in E)$ . Then, for each right-node $v\in V$ , one selects exactly one neighboring edge $e\in N(v)$ , wherein each edge is selected with probability $x_{e}$ . We refer to this as independent rounding. (Here, $N(v)$ denotes the set of edges incident on vertex $v$ ). This algorithmic approach applies to a wide range of problems, and we do not need to belabor its power.

An inherent limitation of independent rounding is that the left-nodes (e.g. the machines in a scheduling problem) can become unevenly loaded due to random fluctuations in edge selections. This is alleviated when the average number of selected edges per left-node is large, but not all problems lie in the “concentration threshold” regime.

In a breakthrough result, [3] devised a new rounding approach, based on dependent rounding with strong negative correlation. Instead of right-nodes acting independently, they are tied together in a scheme wherein each edge $e$ is still marginally selected with probability $x_{e}$ , but for any pair of edges $e, f$ incident on the same left node, there is a strong negative correlation, i.e.

\mathbb{E}[X_{e}X_{f}]\leq(1-c)x_{e}x_{f}

for some small constant $c>0$ , where $X_{e},X_{f}$ are indicator variables for selecting edges $e, f$ . We contrast this with mere negative correlation, which ensures only that

\mathbb{E}[X_{e}X_{f}]\leq x_{e}x_{f}

The strong negative correlation property implies that the loads on each left-node become more balanced. Using this approach, [3] achieved a $(1.5-\varepsilon)$ -approximation algorithm for a classical scheduling problem of minimizing weighted completion time on unrelated machines, for some minuscule constant $\varepsilon>0$ . Notably, they showed that independent rounding – even when given a solution $\vec{x}$ which is a convex combination of optimal integral solutions – is inherently limited to a $1.5$ -approximation ratio.

Since then, a variety of rounding schemes with strong negative correlation have been developed, leading to improved approximation ratios for this scheduling problem and others [9, 8, 5, 7]. Generally speaking, we can group these schemes into two classes. The first approach, as in the original work of [3], is based on a random walk: at each stage, the fractional vector $\vec{x}$ is modified, until eventually it becomes integral. An improved version of this rounding scheme was later developed in [5].

The second approach, developed originally by [8], is based on ideas from contention-resolution in economics. Here, each left-node is “bidding” for the right-nodes, and these demands are balanced so that each left-node does not get too many edges. As a result, the variables $X_{e},X_{f}$ become negatively correlated. The algorithm of [8] was based on Poissonian “tickets” for the allocation; the later work [7] was based on a multivariate geometric distribution.

1.1 Our Contributions

In this work, we develop a new randomized rounding method that falls firmly into the second approach, which we call the Dirichlet mechanism. It is based on Dirichlet random variables as the underlying probability distribution for contention among the left-nodes. Such random variables have powerful properties: they have continuous CDF’s, are negatively associated, are infinitely divisible, can be simulated online, and so on.

The correlation function does not have a closed-form expression, and requires some grueling analysis of the Incomplete Beta function for general calculations. For many algorithmic applications, as we will see, the worst-case behavior comes when the fractional relaxation $\vec{x}$ has infinitesimal entries. In this special case, we can summarize the new algorithm crisply:

Theorem 1 (Simplified).

Suppose that edges $e, f$ share a left-node $u$ , and entries $x_{e},x_{f}$ are infinitesimal. Then the dependent rounding ensures that¹¹1See Proposition 8 and Theorem 11 for further details. For readability, we use the generalized Binomial coefficient here.

\mathbb{E}[X_{e}X_{f}]\leq\frac{x_{e}x_{f}}{\binom{2/a}{1/a}}\qquad\text{for $% a=\sum_{e\in N(u)}x_{e}$}

By contrast, the rounding scheme in [7] would give $\mathbb{E}[X_{e}X_{f}]\leq\frac{2x_{e}x_{f}}{1+e^{1/a}}$ in the infinitesimal setting. The rounding schemes of [3, 9, 5] have not been analyzed for general values of $a$ ; for $a=1$ , they would give coefficients of $\frac{107}{108},\frac{2}{\mathrm{e}}$ and $\frac{26}{27}$ respectively, which apply also for non-infinitesimal $x_{e},x_{f}$ .

At a high level, our approach is similar to [7]: we construct random variables for each edge that are marginally continuous uniform random variables, but collectively have strong negative correlation. Instead of generating them via the Multivariate Geometric distribution, we use a Dirichlet distribution. The new algorithm is quantitatively stronger. It is also simpler: because the Dirichlet distribution has a continuous CDF, there is no need for the tie-breaking mechanisms required in [8] or [7].

By plugging our new dependent-rounding algorithm into the framework of [7], we obtain an improved approximation algorithm for the problem of Scheduling on Unrelated Machines to Minimize Weighted Completion Time, essentially for free. In addition, our new rounding algorithm can be used for a novel, and much simpler, algorithm for the problem of Oblivious Online Matching. We now provide an overview of these problems, and how our algorithm applies to each.

1.2 Application: Oblivious Online Matching

The online dependent rounding problem was introduced in [13], as an abstraction of allocation problems with long-term average-case demand information. In this scenario, we have a bipartite graph $G=(U\cup V,E)$ , where the “offline nodes” $U$ are fixed and known in advance. Each time an “online” node $v\in V$ appears, we learn the demand values $g_{(u,v)}:u\in U$ . We are guaranteed that the overall collection of demands $g_{e}$ forms a fractional matching in the graph. Upon the arrival of $v$ we must immediately and irrevocably select some edge $e$ incident to $v$ to add to a matching $M$ (or opt to add none). The goal is to achieve

\Pr(e\in M)\geq\gamma\thinspace g_{e}\qquad\text{for some factor $\gamma\in[0,% 1]$}

In the offline setting, it is trivial to achieve a ratio $\gamma=1$ , since the fractional matching polytope has no integrality gap for bipartite graphs. There is a simple online scheme to achieve a ratio $\gamma=1-1/e\approx 0.632$ , based on contention resolution. The work [13] showed an upper-bound for $\gamma\leq 0.828$ in the online setting, and provided a sophisticated algorithm with ratio $\gamma=0.652$ .

The Dirichlet mechanism can be implemented in the online setting, which we use to provide an improved algorithm for this problem. We get the following result:

Theorem 2.

There is an algorithm for Oblivious Online Matching with ratio $\negthinspace\gamma=0.68$ .

Beyond the slightly improved factor, the algorithm is simpler. Unlike [13], it does not need special cases and subroutines; the full algorithm fits comfortably on half a page. We emphasize that this is the first new application of strongly negatively correlated randomized rounding schemes since its introduction in [3].

1.3 Application: Weighted Completion Time

The classical scheduling problem of Weighted Completion Time on Unrelated Machines is denoted in the scheduling literature as $R||\sum_{j}w_{j}C_{j}$ . We have a set of machines $\mathcal{M}$ and a set of jobs $\mathcal{J}$ , where each job $j$ has a weight $w_{j}$ and a separate processing time $p_{ij}$ on each machine $i$ . The objective is to assign jobs to machines in some order, so as to minimize the total weighted completion time $\sum_{j}w_{j}C_{j}$ , where $C_{j}$ is the cumulative processing time of all jobs assigned to machine $i$ up to and including $j$ , $\sum_{j^{\prime}\leq j}p_{ij^{\prime}}$ . There is also a variant where the weight of a job $j$ may depend on the machine $i$ to which it is assigned.

This problem has attracted attention, in part, because it leads to sophisticated rounding algorithms. In particular, the objective function can be seen as a quadratic function of the underlying assignment variables. Breaking a long-standing barrier, [3] devised a rounding algorithm with an approximation ratio $1.5-\varepsilon$ for a very small constant $\varepsilon>0$ , based on dependent rounding with negative correlation.

Since then, there have been a number of improved approximation algorithms using various dependent rounding schemes. Most of these works can be summarized in the following framework: first solve a convex relaxation, next cluster the jobs by processing times and weights, and finally apply a rounding scheme with strong negative correlation within clusters. (The recent algorithm [12] is an exception to this pattern: it is more in the genre of iterated rounding.) We summarize these algorithms as follows:

Ref.	Relaxation	Machine-varying	Ratio
		weights?
[3]	Semidefinite Program	$\checkmark$	$1.5-\varepsilon$
[11]	Time-indexed LP	$\checkmark$	$1.5-\varepsilon$
[9]	Time-indexed LP	$\checkmark$	$1.488$
[8]	Time-indexed LP	$\checkmark$	$1.45$
[7]	Semidefinite Program	$\checkmark$	$1.398$
[12]	Configuration LP	X	$1.36$
This work	Semidefinite Program	$\checkmark$	$1.387^{\dagger}$

Plugging the Dirichlet mechanism into the algorithm of [7] gives us a slightly stronger approximation ratio, essentially for free.²²2Since our analysis is very similar to [7], we used off-the-shelf numerical optimization methods instead of exact arithmetic for the computations. As a result, the numerical figure here is technically a pseudo-theorem (marked with a dagger).

2 Preliminaries

In this section we review background on two key probabilistic notions used throughout the paper: (i) Negative Association of random variables, and (ii) the Dirichlet distribution and its properties.

At several points in this paper, we silently assume that relevant quantities are non-zero. For example, we may write $\frac{1}{x}-1$ without verifying that $x>0$ . In all cases, the formulas can be extended to the boundary case $x=0$ in a straightforward way. This convention allows us to avoid cluttering the exposition with excessive edge case discussions.

Our algorithms center around a probability distribution known as the Dirichlet distribution. In order to define it, we first introduce the Beta function,

\operatorname{B}(a;b)=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)}=\int_{0}^{1}t^{a-% 1}(1-t)^{b-1}\ \mathrm{d}t

where $\Gamma$ denotes the Gamma function. This is closely related to the generalized Binomial coefficient defined by

\binom{x}{y}:=\frac{\Gamma(x+1)}{\Gamma(y+1)\Gamma(x-y+1)}=\frac{1}{\mathrm{B}% (x-y;y+1)(x-y)}

There are a number of important variants and extensions of the Beta function that will be useful for our analysis. The first is the Incomplete Beta function, given by

\operatorname{B}(z;a;b)=\int_{0}^{z}t^{a-1}(1-t)^{b-1}\ \mathrm{d}t=z^{a}\sum_% {k=0}^{\infty}\frac{\Gamma(k+1-b)z^{k}}{\Gamma(1-b)(a+k)k!}.

where the latter a convergent series for $|z|<1$ . We also define the regularized Incomplete Beta function by

I(z;a;b)=\frac{\operatorname{B}(z;a;b)}{\operatorname{B}(a;b)}.

Another variant is the multivariate Beta function, defined for a vector $\vec{\rho}=(\rho_{0},\dots,\rho_{n})$ by

\operatorname{B}(\vec{\rho})=\frac{\prod_{i=0}^{n}\Gamma(\rho_{i})}{\Gamma% \left(\sum_{i=0}^{n}\rho_{i}\right)}

Definition 3 (Dirichlet distribution).

The Dirichlet distribution is a family of continuous multivariate probability distributions parameterized by a vector of positive reals $\vec{\rho}=(\rho_{1},\rho_{2},\dots,\rho_{n})$ . It is denoted as $\operatorname{Dir}(\vec{\rho})$ and defined on the $(n-1)$ -dimensional simplex by the probability density function

f(x_{1},\dots,x_{n};\rho_{1},\dots,\rho_{n})=\frac{1}{\operatorname{B}(\vec{% \rho})}\prod_{i=1}^{n}x_{i}^{\rho_{i}-1}

where $x_{i}\geq 0$ , $\sum_{i=1}^{n}x_{i}=1$ .

The Dirichlet distribution can be viewed as a distribution over vectors with $x_{1}+\dots+x_{n}\leq 1$ , with PDF:

f(x_{1},\dots,x_{n};\rho_{1},\dots,\rho_{n},\rho_{0})=\frac{1}{\operatorname{B% }(\vec{\rho})}(1-x_{1}-\dots-x_{n})^{\rho_{0}-1}\prod_{i=1}^{n}x_{i}^{\rho_{i}% -1}

for $\vec{\rho}=(\rho_{1},\dots,\rho_{n},\rho_{0})$ . This effectively adds a dummy variable $x_{0}$ as the $(n+1)^{\text{st}}$ dimension to lie on the $n$ -dimensional simplex.

The following important property will be used for our Dirichlet rounding algorithm:

Definition 4 (Negatively Associated random variables).

A finite collection of random variables $\chi=(X_{1},X_{2},\dots,X_{n})$ is negatively associated (NA) if for every pair of disjoint subsets $A,B\subseteq[n]$ , we have

\mathbb{C}\text{ov}(f(X_{i},i\in A),g(X_{j},j\in B))\leq 0

for all functions $f$ and $g$ that are increasing in each argument.

Fact 5 (Properties of the Dirichlet distribution).

Let $(X_{1},\dots,X_{n})\sim\operatorname{Dir}(\rho_{1},\dots,\rho_{n})$ .

1.

Marginals have a Beta distribution: Each coordinate $i$ satisfies $X_{i}\sim\operatorname{Beta}(\rho_{i},\sum_{j\neq i}\rho_{j})$ . Its CDF is given by

$\Pr(X_{i}\leq z)=I(z;\rho_{i},\sum_{j\neq i}\rho_{j})\qquad\text{for $z\in[0,1% ]$}.$
2.

Symmetry: If $\pi$ is a permutation of $\{1,\dots,n\}$ , then $(X_{\pi 1},\dots,X_{\pi n})\sim\operatorname{Dir}(\rho_{\pi 1},\dots,\rho_{\pi n})$ .
3.

Aggregation: If two components $X_{i}$ and $X_{j}$ are aggregated by summation, with $X_{i}$ and $X_{j}$ replaced by $X_{i}+X_{j}$ , the new vector $X^{\prime}=(X_{1},\ldots,X_{i}+X_{j},\ldots,X_{n})$ also follows a Dirichlet distribution,

$X^{\prime}\sim\operatorname{Dir}(\rho_{1},\ldots,\rho_{i}+\rho_{j},\ldots,\rho% _{n}).$
4.

Neutrality: For any $k\leq n$ , the random variable $X_{k}$ is independent of

$\left(\frac{X_{1}}{1-X_{k}},\dots,\frac{X_{k-1}}{1-X_{k}},\frac{X_{k+1}}{1-X_{% k}},\dots,\frac{X_{n}}{1-X_{k}}\right).$
5.

Negative association: $X_{1},\dots,X_{n}$ are NA r.v.’s [4]
6.

Moments: For a vector of non-negative reals $\vec{\beta}=(\beta_{1},\dots,\beta_{n})$ , there holds

$\mathbb{E}\left[\prod_{i=1}^{n}X_{i}^{\beta_{i}}\right]=\frac{\operatorname{B}% (\vec{\rho}+\vec{\beta})}{\operatorname{B}(\vec{\rho})}=\frac{\Gamma\left(\sum% _{i=1}^{n}\rho_{i}\right)}{\Gamma\left(\sum_{i=1}^{n}\rho_{i}+\beta_{i}\right)% }\prod_{i=1}^{n}\frac{\Gamma(\rho_{i}+\beta_{i})}{\Gamma(\rho_{i})},$

where $\operatorname{B}(\vec{\rho})$ is the multivariate beta function.

3 The Dirichlet mechanism

We introduce the Dirichlet mechanism for bipartite rounding. It has two parts. The first part is the generation of a vector of negatively correlated uniform random variables. This is achieved by sampling Dirichlet variables, and transforming them into uniform random variables. The second part is a method of bipartite selection using these generated Uniform random variables. This rounding step is exactly the same as the method of [7]; for completeness, we include the analysis in this section.

3.1 The Dirichlet copula

This step is deceptively simple: generate a multivariate Dirichlet vector and transform each of its marginals to a Uniform. The resulting probability distribution is known as a copula. Here we use Fact 5(1), which gives the explicit marginal CDF in terms of the regularized Incomplete Beta function $I(z;\rho_{i};1-\rho_{i})$ .

Algorithm 1 DirichletCopula(

\vec{\rho}

).

Observation 6.

Each variable $A_{i}$ follows the distribution $\text{Unif}([0,1])$

Proof.

By Fact 5(1), each $T_{i}$ is marginally distributed as $\text{Beta}(\rho_{i};1-\rho_{i})$ with CDF $I(x,\rho_{i},1-\rho_{i})$ . Note that $I(x,\rho_{i},1-\rho_{i})$ is a continuous function of $x$ . Thus, the mapping from $T_{i}$ to $A_{i}$ is the well-known inverse transform sampling for random variables. $\hfill\blacktriangleleft$

Most of the analysis can be stated in terms of a function $\Psi$ , which is intuitively some measure of the correlation between the random variables $A_{i}$ and $A_{j}$ . This function is used throughout the analysis, and we will need the integral form of it for analysis later:

Proposition 7.

For indices $i\neq j$ and $x_{i},x_{j}>0$ , we have

\mathbb{E}[A_{i}^{1/x_{i}-1}A_{j}^{1/x_{j}-1}]=x_{i}x_{j}\Psi(x_{i},x_{j};\rho% _{i},\rho_{j})

for the function $\Psi$ defined as $\Psi(x_{1},x_{2};\rho_{1},\rho_{2})=\mathbb{E}[I(X_{1};\rho_{1};1-\rho_{1})^{1% /x_{1}-1}I(X_{2};\rho_{2},1-\rho_{2})^{1/x_{2}-1}]$ where $X_{1},X_{2}\sim\text{Dir}(\rho_{1},\rho_{2},1-\rho_{1}-\rho_{2})$ .

Proof.

We have $(T_{i},T_{j})\sim\text{Dir}(\rho_{i},\rho_{j},1-\rho_{i}-\rho_{j})\sim(X_{1},X% _{2})$ by Fact 5(2). $\hfill\blacktriangleleft$

The $\Psi$ function is critical to analyzing the approximation factors of the algorithms. Unfortunately, it is extremely complex, defined in terms of integrals and non-elementary functions. As a rough order-of-magnitude estimate, the following bound is useful:

Proposition 8.

There holds

\Psi(x_{1},x_{2};\rho_{1},\rho_{2})\leq\binom{\rho_{1}(1/x_{1}-1)+\rho_{2}(1/x% _{2}-1)}{\rho_{1}(1/x_{1}-1)}^{-1}.

By contrast, note that independent uniform random variables $U_{1},U_{2}$ would have

\mathbb{E}[U_{1}^{1/x_{1}-1}U_{2}^{1/x_{2}-1}]=x_{1}x_{2}.

Since $\binom{\rho_{1}(1/x_{1}-1)+\rho_{2}(1/x_{2}-1)}{\rho_{1}(1/x_{1}-1)}>1$ , Proposition 8 should be interpreted as a statement that the correlated uniform random variables $A_{1}$ and $A_{2}$ have strong negative correlation.

We show Proposition 8 in Section 6, along with other more-precise (but complicated) bounds. For now, we think of $\Psi$ as a black-box function, and we calculate the algorithm’s behavior in terms of $\Psi$ . We will later use more-precise versions of Proposition 8 to give explicit bounds for our algorithms.

3.2 Bipartite rounding

The second part of the Dirichlet mechanism is to implement bipartite selection using the correlated uniform variables. We start with a bipartite graph $G=(U\cup V,E)$ , with weight $x_{e}$ and a correlation parameter $\rho_{e}$ for each edge $e$ . These are generated in a problem-specific way; intuitively, $\rho_{e}$ controls how much “repulsion” the edge has toward other edges sharing the same left-node.

At a high level, each left-node $u$ generates uniform random variables $A_{e}$ for the edges $e\in N(u)$ via CorrelatedUniform. It then transforms these uniform variables to exponential variables $Z_{e}$ with rate $x_{e}$ . Each right-node $v$ selects the incident edge whose value $Z_{e}$ is the smallest. (If $x(N(u))<1$ then there is a slight adjustment where $u$ may select no edges.)

If the exponential random variables $Z_{e}$ were all independent, then this would be equivalent to independent rounding; this is known as randomized rounding via exponential clocks in the literature [1]. Intuitively, it is beneficial to negatively correlate the events that two adjacent edges are added, as this reduces the expected number of collisions and hence the need to subsequently remove edges to obtain a valid matching.

Combining the new sampling scheme with the algorithm from [7], we introduce Algorithm 2.

Algorithm 2 DepRound(

G,\vec{x},\vec{\rho}

): the Dirichlet rounding mechanism.

Lines 3 and 4 are precisely applying DirichletCopula for the vector $(\rho_{e}:e\in N(e))$ . Note that in Line 8, if $x(N(v))=1$ , the condition reduces to choosing the minimum $Z_{f}$ value. To state the negative correlation results in greatest generality, we recall the following definition and lemma from [7].

Definition 9 (Stable edge set).

An edge set $S\subseteq E$ of $G$ is stable if it has no edges $e_{1},e_{2}$ whose distance in the line graph of $G$ is precisely two.

Lemma 10 ([7]).

Algorithm 2 satisfies the following properties:

1.

For any right-node $v\in V$ , the random variables $Z_{e}:e\in N(v)$ are independent Exponentials, each of rate $x_{e}$ .
2.

The random variables $A_{e}:e\in E$ are NA.
3.

For any edge $e\in E$ , there holds $\Pr[X_{e}=1]=x_{e}$ .
4.

Each right-node $v$ has at most one edge selected.
5.

For a stable edge set $S$ , there holds $\mathbb{E}\bigl[\prod_{e\in S}X_{e}\bigr]\leq\mathbb{E}\bigl[\prod_{e\in S}A_{% e}^{1/x_{e}-1}\bigr]\leq\prod_{e\in S}x_{e}.$

Proof.

The proofs are similar to [7] and are deferred to Appendix C. $\hfill\blacktriangleleft$

The following theorem characterizes the strong negative correlation properties of the algorithm entirely based on the $\Psi$ function.

Theorem 11.

For any two edges $e_{1}=(u,v_{1})$ , $e_{2}=(u,v_{2})$ with the same left-node $u$ we have

\mathbb{E}[X_{e_{1}}X_{e_{2}}]\leq x_{e_{1}}x_{e_{2}}\Psi(x_{e_{1}},x_{e_{2}};% \rho_{e_{1}},\rho_{e_{2}})

Proof.

Note that $S=\{e_{1},e_{2}\}$ is a stable edge-set, since $e_{1}$ and $e_{2}$ have distance one in the line graph of $G$ . By Lemma 10, we have $\mathbb{E}[X_{e_{1}}X_{e_{2}}]\leq\mathbb{E}\bigl[A_{e_{1}}^{1/x_{e_{1}}-1}A_{% e_{2}}^{1/x_{e_{2}}-1}\bigr].$ The random variables $A_{e_{1}},A_{e_{2}}$ are generated by DirichletCopula with input $\vec{\rho}$ . So the result follows from Proposition 7. $\hfill\blacktriangleleft$

4 Online Matching algorithm

Recall the problem setting: we have a bipartite graph $G=(U\cup V,E)$ , where the offline nodes $U$ are fixed and known in advance. When each online node $v\in V$ appears, we learn the demands $g_{(u,v)}:u\in U$ . We are guaranteed that the weights $g_{e}$ form a fractional matching for the graph.

For edges $e_{1}=(u_{1},v_{1}),e_{2}=(u_{2},v_{2})$ , we say that $e_{1}<e_{2}$ if the online node node $v_{1}$ is revealed before $v_{2}$ . For an edge $e=(u,v)$ , we define $L(e)=\{f\in N(u),f<e\}$ , that is, edges which share a left-node with $e$ and come earlier in the ordering.

Our plan is to run $\textsc{DepRound}(G,\vec{x},\vec{\rho})$ , where $\vec{x}$ and $\vec{\rho}$ are both determined in an online fashion from $\vec{g}$ . For this, we take advantage of the fact that the generation of Dirichlet random variables, and the DepRound algorithm, can both be implemented online vertex-by-vertex. For full details see Algorithm 3.

Algorithm 3 ExponentialODRS(

\{x_{e}\in[0,1]:e\in E\}

).

For intuition, suppose all values $g_{e}$ are infinitesimal. In this case, $x_{e}\approx F(r_{e})g_{e}\approx y_{e}$ for each edge $e$ . The function $F$ serves as an “attenuation factor” so that edge $e$ is selected with probability $x_{e}\approx F(r_{e})g_{e}$ , as opposed to $g_{e}$ in an offline algorithm. Without this attenuation factor, the early arriving edges would go into the matching with a higher probability, as later ones can only be accepted if no earlier edge was selected. The factor $F(t)$ penalizes earlier edges (where $r_{e}\approx 0$ and $F(r_{e})\approx F(0)=0.68145$ ), while leaving alone the final edges of a node (where $r_{e}\approx 1$ and $F(r_{e})\approx 1$ ). This evens out the edges; as a side benefit, the attenuation factor increases the negative correlation strength of the Dirichlet mechanism.

To derive the specific functional form of $F$ , we assume the edge weights $g_{e}$ are infinitesimal, and solve a differential equation to maximize the minimum approximation ratio. See Appendix B for further details.

Let us define

Q(t_{0},\Delta t)=\int_{t=t_{0}}^{t_{0}+\Delta_{t}}F(t)\ \mathrm{d}t,\qquad% \text{so that $y_{e}=Q(r_{e},g_{e})$.}

By direct calculations, one can easily verify the following properties of the function $F$ :

Observation 12.

The function $F$ satisfies the following properties:

(a)

$F$ is nonnegative, increasing, and concave-up;
(b)

$Q(0,1)\leq 1/\alpha$ ;
(c)

$F(1)\leq 1$ .

We now examine a few basic properties and inequalities of the algorithm. On a high level, we first show that the choice of edges in ExponentialODRS is exactly the same as running DepRound, for suitable choice of parameters. This gives us Observation 16, which enables us to reduce the analysis of the algorithm to analyzing the $\Psi$ function.

Proposition 13.

For an edge $e$ there holds $r_{e}=\sum_{f\in L(e)}g_{f}$ and $r_{e}+g_{e}\leq 1$ and $\sum_{f\in L(e)}y_{f}=Q(0,r_{e})$

Proof.

Let $u$ denote the left-node of $e$ and let the edges adjacent to $u$ be $f_{1},f_{2},\dots,f_{k},e$ in order of arrival. So $r_{e}=g_{f_{1}}+\dots+g_{f_{k}};$ since $x$ is a fractional matching this is at most $1-g_{e}$ . We further compute:

		$\displaystyle y_{f_{1}}+\dots+y_{f_{k}}=Q(r_{f_{1}},g_{f_{1}})+Q(r_{f_{2}},g_{% f_{2}})+\dots+Q(r_{e},g_{e})$
		$\displaystyle\qquad=Q(0,g_{f_{1}})+Q(g_{f_{1}},g_{f_{2}})+\dots+Q(g_{f_{1}}+% \dots+g_{f_{k-1}},g_{f_{k}})$
		$\displaystyle\qquad=\int_{t=0}^{g_{f_{1}}}F(t)\ \mathrm{d}t+\int_{t=g_{f_{1}}}% ^{g_{f_{1}}+g_{f_{2}}}F(t)\ \mathrm{d}t+\dots+\int_{t=g_{f_{1}}+\dots+g_{f_{k-% 1}}}^{g_{f_{1}}+\dots+g_{f_{k}}}F(t)\ \mathrm{d}t$
		$\displaystyle\qquad=\int_{t=0}^{g_{f_{1}}+\dots+g_{f_{k}}}F(t)\ \mathrm{d}t=Q(% 0,r_{e}).\$

$\hfill\blacktriangleleft$

Proposition 14.

For each edge $e$ there holds $x_{e}\geq 0$ and $\rho_{e}\geq 0$ .

For each right-node $v$ there holds $\sum_{e\in N(v)}x_{e}\leq 1$ .

For each left-node $u$ there holds $\sum_{e\in N(u)}\rho_{e}\leq 1$ .

Proof.

Non-negativity of $x$ and $\rho$ hold since $F$ is non-negative. For each edge $e$ , convexity and monotonicity of $F$ implies that

x_{e}=(1-\beta)g_{e}F(r_{e})+\beta\int_{t=r_{e}}^{r_{e}+g_{e}}F(t)\ \mathrm{d}% t\leq g_{e}F(1)\leq g_{e}.

Therefore, for a right-node $v$ , we have $\sum_{e\in N(v)}x_{e}\leq\sum_{e\in N(v)}g_{e}=g(N(v))\leq 1$ where the last inequality holds since $g$ is a fractional matching of $G$ .

For the second bound, considering adding an additional dummy edge $e$ at the end of $u$ . By Proposition 13 and Observation 12, we calculate $\sum_{f\in N(u)}\rho_{e}=\sum_{f\in L(e)}\alpha y_{f}=\alpha Q(0,r_{e})\leq% \alpha Q(0,1)\leq\alpha\cdot\frac{1}{\alpha}=1.$ $\hfill\blacktriangleleft$

Let us say now that an edge $e=(u,v)$ is selected if $(1-x_{e})Z_{e}<(x(N(v))-x_{e})\min_{f\in N(v)\setminus\{e\}}Z_{f}$ , (i.e. it satisfies the inequality at Line 8); the edge may or may not be added to the matching, depending on whether $u\in U$ has been matched earlier.

Lemma 15.

Let $X_{e}$ denote the indicator variable that edge $e$ is selected. The random variables $X_{e}:e\in E$ are as produced by algorithm $\vec{X}\leftarrow\textsc{DepRound}(G,\vec{x},\vec{\rho})$ .

Proof.

The generation of $T$ in the algorithm follows from the well-known “stick-breaking process” for the Dirichlet distribution [6]. For completeness, we sketch a proof.

Let $u$ be a left-node with edges $e_{1},e_{2},\dots,e_{k}$ in order of arrival. By Proposition 14 we have $\sum_{e\in N(u)}\rho_{e}\leq 1$ . Let $T_{e_{1}},\dots,T_{e_{k}}$ be random variables as defined in ExponentialODRS and let $(T^{\prime}_{e_{1}},\dots,T^{\prime}_{e_{k}})$ be corresponding Dirichlet variables as in DirichletCopula. We claim by induction that

(T_{e_{1}},\dots,T_{e_{i}})\sim\operatorname{Dir}(\rho_{e_{1}},\dots,\rho_{e_{% i}},1-\rho_{e_{1}}-\dots-\rho_{e_{i}}).

For, Fact 5(4) shows that $\frac{(T^{\prime}_{e_{i}}|T^{\prime}_{e_{1}},\dots,T^{\prime}_{e_{i-1}})}{1-% \sum_{j=1}^{i-1}T^{\prime}_{e_{j}}}$ has the same distribution as $\operatorname{Beta}(\rho_{e_{i}},1-\sum_{j=1}^{i-1}\rho_{e_{j}})$ , and $T_{e_{i}}$ is drawn according to this distribution. By Fact 5(3) we aggregate the remaining coordinates $T^{\prime}_{e_{i+1}},\dots,T^{\prime}_{e_{k}}$ , hence $(T_{e_{1}},\dots,T_{e_{i}})$ has precisely the same distribution as $(T^{\prime}_{e_{1}},\dots,T^{\prime}_{e_{i}})$ .

By Fact 5(2), the overall distribution of $(T_{e})_{e\in N(u)}$ is thus the same as in DirichletCopula. $\hfill\blacktriangleleft$

From Lemma 15, we get the following immediate consequences:

Observation 16.

1.

$M$ is a matching.
2.

Each edge $e$ is selected with probability exactly $x_{e}$ .
3.

Edges $e, f$ sharing a left-node are jointly selected with probability at most
$x_{e}x_{f}\Psi(x_{e},x_{f};\rho_{e},\rho_{f})$ .

The following calculation is now key to the approximation ratio:

Lemma 17.

For values $r_{1},r_{2},g_{1},g_{2}\geq 0$ with $g_{2}+r_{2}\leq r_{1},g_{1}+r_{1}\leq 1$ , and corresponding values

y_{i}=Q(r_{i},g_{i}),\qquad x_{i}=(1-\beta)F(r_{i})g_{i}+\beta y_{i},\qquad% \rho_{i}=ay_{i}

there holds

\Psi(x_{1},x_{2};\rho_{1},\rho_{2})x_{1}x_{2}\leq c\cdot F(r_{1})g_{1}y_{2}+% \frac{\beta(y_{1}-g_{1}F(r_{1}))y_{2}}{Q(0,r_{1})}\qquad\qquad\text{for % constant $c=0.3947$}

Showing this requires a grid search over the relevant parameters $g_{1},g_{2},r_{1},r_{2}$ and massive computer calculation, as discussed in the full version of the paper. It immediately gives us the bound on the approximation ratio:

Theorem 18.

Each edge $e$ goes into the matching with probability at least $0.68\thinspace g_{e}$ .

Proof.

We have $e\in M$ if $e$ is selected and there is no earlier edge $f\in L(e)$ which is selected. So $\Pr(e\in M)\geq\mathbb{E}[X_{e}]-\sum_{f\in L(e)}\mathbb{E}[X_{e}X_{f}]$

Let $z=\beta(y_{e}-F(r_{e})g_{e})$ and let $s=Q(0,r_{e})$ . By Observation 16 and Lemma 17, we have

	$\displaystyle\mathbb{E}[X_{e}]$	$\displaystyle=x_{e}=F(r_{e})g_{e}+z$
	$\displaystyle\mathbb{E}[X_{e}X_{f}]$	$\displaystyle\leq y_{f}(cF(r_{e})g_{e}+z/s)$

Thus, overall

$\displaystyle\Pr(e\in M)$	$\displaystyle\geq F(r_{e})g_{e}+z-\negthickspace\sum_{f\in L(e)}\negthickspace y% _{f}\bigl(cF(r_{e})g_{e}+z/s\bigr)$
	$\displaystyle=z+g_{e}F(r_{e})-s(cF(r_{e})g_{e}+z/s)$	(Proposition 13)
	$\displaystyle=g_{e}F(r_{e})(1-c\int_{t=0}^{r_{e}}F(t)\ \mathrm{d}t)$	(definition of $s$ )

It can be easily checked that $F(r)(1-c\int_{t=0}^{r}F(t)\ \mathrm{d}t)\geq 0.68$ for all $r\in[0,1]$ . $\hfill\blacktriangleleft$

5 Weighted completion time on unrelated machines

To reiterate and set notation, we have a set of machines $\mathcal{M}$ and a set of jobs $\mathcal{J}$ . Each machine-job pair $(i,j)$ has a weight $w^{(i)}_{j}$ and processing time $p^{(i)}_{j}$ . The objective is to schedule jobs to minimize

\text{OBJ}=\sum_{i}\sum_{\begin{subarray}{c}\text{jobs $j$ assigned}\\ \text{to machine $i$}\end{subarray}}w_{j}^{(i)}C_{j},

where $C_{j}$ is the cumulative processing time on machine $i$ for all jobs assigned up to and including job $j$ .

For a single machine, the problem can be solved with a well-known greedy heuristic: schedule the jobs in a decreasing order of the Smith ratio $\sigma_{j}=w_{j}/p_{j}$ . Thus, the key task is to determine which machine to allocate each task to.

Our algorithm starts with a semidefinite-programming (SDP) relaxation, yielding fractional assignments $x_{j}^{(i)}$ for each pair $(i,j)$ . The precise form of this program is not relevant for us; see [3] for details. Next, we use the clustering algorithm from [7]: the jobs on each machine are partitioned into classes $\mathcal{P}^{(i)}$ based on their processing times; to avoid worst-case behavior this is done via a random shift. Within each class $\mathcal{P}^{(i)}$ , the jobs are sorted in descending order of their Smith ratios $\sigma_{j}^{(i)}=w_{j}^{(i)}/p^{(i)}_{j}$ , and sequentially added to a cluster until the cumulative weight of the cluster, $\sum_{j\in\mathcal{C}}x_{j}^{(i)}$ , surpasses a threshold $\theta$ .

We obtain the integral solution $\vec{X}^{(i)}_{j}$ using the DepRound algorithm, where each edge $e$ represents a possible assignment of a job $j$ to a cluster $\mathcal{C}^{(i)}_{k,\ell}$ (and hence to machine $i$ ). Most of the rates $\rho_{e}$ are proportional to $x^{(i)}_{j}$ , however, the last job added to a cluster requires special handling when the cumulative weight of the cluster exceeds a larger threshold $\tau>\theta$ . We refer to this as a truncated job (there can be at most one per cluster), and the others as untruncated jobs.

The full details are in Algorithm 4.

Algorithm 4 Clustering for the scheduling algorithm.

The subsequent discussion relies on the following key fact.

Theorem 19 ([3]).

For any machine $i^{*}$ , suppose the jobs $1,\ldots,n$ are sorted in descending order of the Smith ratio $\sigma_{j}^{\left(i^{*}\right)}$ . For each job $j^{*}$ , define

	$\displaystyle Z^{\left(i^{},j^{}\right)}$	$\displaystyle=\frac{1}{2}\left(\sum_{j=1}^{j^{}}X_{j}^{\left(i^{}\right)}% \left(p_{j}^{\left(i^{}\right)}\right)^{2}+\sum_{j=1}^{j^{}}\sum_{j^{\prime}% =1}^{j^{}}X_{j}^{\left(i^{}\right)}X_{j^{\prime}}^{\left(i^{}\right)}p_{j}^% {\left(i^{}\right)}p_{j^{\prime}}^{\left(i^{*}\right)}\right)$
	$\displaystyle\mathrm{LB}^{\left(i^{},j^{}\right)}$	$\displaystyle=\frac{1}{2}\left(\sum_{j=1}^{j^{}}x_{j}^{\left(i^{}\right)}% \left(p_{j}^{\left(i^{}\right)}\right)^{2}+\sum_{j=1}^{j^{}}\sum_{j^{\prime}% =1}^{j^{}}x_{j,j^{\prime}}^{\left(i^{}\right)}p_{j}^{\left(i^{}\right)}p_{j% ^{\prime}}^{\left(i^{}\right)}\right)$

If $\mathbb{E}[Z^{\left(i^{*},j^{*}\right)}]\leq\eta\cdot\mathrm{LB}^{\left(i^{*},% j^{*}\right)}$ for all $i^{*},j^{*}$ , then the schedule is an $\eta$ -approximation in expectation.

In light of Theorem 19, we focus on a single pair $(i^{*},j^{*})$ . From now on we omit the superscript $(i^{*})$ and $(j^{*})$ from all relevant variables, writing $Z$ , $X_{j}$ , $p_{j}$ , $w_{j}$ , $\sigma_{j}$ , $\mathcal{P}_{k}$ , instead of $Z^{(i^{*},j^{*})}$ , $X_{j}^{(i^{*})}$ , $p_{j}^{(i^{*})}$ , etc.. In addition, all summations $\sum_{j}$ are assumed to range over jobs $j\in\mathcal{J}^{*}$ , the set of jobs whose Smith ratio is less than the target job $j^{*}$ . Similarly, summations $\sum_{j^{\prime},j^{\prime\prime}}$ range over ordered pairs $(j^{\prime},j^{\prime\prime})\in\mathcal{J}^{*}\times\mathcal{J}^{*}$ .

For each processing time class $\mathcal{P}_{k}$ , we define $P_{k}=\pi^{k-P_{\text{offset}}},\mathcal{P}_{k}^{*}=\mathcal{P}_{k}\cap% \mathcal{J}^{*}$ , and similarly for each cluster $\mathcal{C}_{k,\ell}$ , we set $\mathcal{C}_{k,\ell}^{*}=\mathcal{C}_{k,\ell}\cap\mathcal{J}^{*}$ . The last cluster opened within $\mathcal{P}_{k}^{*}$ is called a leftover cluster (it could be empty) and is denoted by $\mathcal{C}_{k,\text{left}}^{*}$ . For a job $j\in\mathcal{P}_{k}^{(i)}$ , we define $H_{j}=p_{j}/P_{k}\in[1,\pi]$ .

Proposition 20.

For any pair of jobs $j,j^{\prime}$ , we have $\mathbb{E}[X_{j}X_{j^{\prime}}]\leq x_{j}x_{j^{\prime}}$ . Moreover, if $j,j^{\prime}$ are both in the same cluster, then $\mathbb{E}[X_{j}X_{j^{\prime}}]\leq x_{j}x_{j^{\prime}}\Psi(x_{j},x_{j^{\prime% }};\rho_{j},\rho_{j^{\prime}})$ .

Proof.

If jobs $j,j^{\prime}$ are in clusters $\mathcal{C}^{(i^{*})}_{k,\ell},\mathcal{C}^{(i^{*})}_{k^{\prime},\ell^{\prime}}$ for machine $i^{*}$ , then $\{((i^{*},k,\ell),j),((i^{*},k^{\prime},\ell^{\prime}),j^{\prime})\}$ is a stable edge set of $G$ , since every job is assigned to a unique cluster per machine. So the first bound follows from Lemma 10. If jobs $j,j^{\prime}$ are in the same cluster, then the edges $((i^{*},k,\ell),j),((i^{*},k,\ell),j^{\prime})$ share the same left-node of $G$ . So the second bound follows from Theorem 11. $\hfill\blacktriangleleft$

Now the objective becomes to bound the upper-bound and lower-bound variables

	$\displaystyle Z$	$\displaystyle=\frac{1}{2}\Bigl(\sum_{j}X_{j}p_{j}^{2}+\sum_{j,j^{\prime}}X_{j}% X_{j^{\prime}}p_{j}p_{j^{\prime}}\Bigr)=\sum_{j}X_{j}p_{j}^{2}+\frac{1}{2}\sum% _{j,j^{\prime}:j^{\prime}\neq j}X_{j}X_{j^{\prime}}p_{j}p_{j^{\prime}}$
	$\displaystyle\mathrm{LB}$	$\displaystyle=\frac{1}{2}\Bigl(\sum_{j}x_{j}p_{j}^{2}+\sum_{j,j^{\prime}}x_{j,% j^{\prime}}p_{j}p_{j^{\prime}}\Bigr)\quad=\sum_{j}x_{j}p_{j}^{2}+\frac{1}{2}% \sum_{j,j^{\prime}:j^{\prime}\neq j}x_{j,j^{\prime}}p_{j}p_{j^{\prime}}.$

We emphasize that $Z$ is a random variable which is determined by two sources of randomness: the offset $P_{\text{offset}}$ used to form the clusters, and the Dirichlet mechanism itself. Conversely, $\mathrm{LB}$ is just a scalar quantity. In order to analyze the lower and upper bounds, we define parameters

L=\sum_{j}x_{j}p_{j},\qquad\qquad Q=\sum_{j}x_{j}p_{j}^{2},

Note that $\mathrm{LB}\geq\max\left\{Q,\frac{1}{2}\left(Q+L^{2}\right)\right\}$ . On the other hand, just using the negative correlation property $E[X_{j}X_{j^{\prime}}]\leq x_{j}x_{j^{\prime}}$ , we have $\mathbb{E}[Z]\leq Q+\frac{1}{2}L^{2}$ . So $\mathbb{E}[Z]\leq 3/2\cdot\mathrm{LB}$ , hence, providing a $1.5$ -approximation.

Our argument closely follows [7], and only a small portion depends on the strong negative correlation itself. In particular, the strong negative correlation property, which is where the Dirichlet mechanism plays a role, leads to an upper bound on $\mathbb{E}[Z]$ expressed in terms of $L, Q$ and some additional parameters. A separate argument provides a lower bound on $\mathrm{LB}$ in terms of the same parameters. Finally, a numerical optimization determines the maximum ratio between these bounds, which is the upper bound on the approximation ratio.

Theorem^† 21.

We have $\mathbb{E}[Z]\leq 1.387\cdot\mathrm{LB}.$ In particular, Algorithm 4 achieves an approximation ratio of $1.387$ in expectation, and the SDP relaxation has integrality gap at most $1.387$ .

The technical details are deferred to the full paper.

6 Analysis of the function $\Psi$

We consider a number of properties of the $\Psi$ function, via analysis of the Incomplete Beta function. This will allow us to compute various limits as well as arbitrarily-accurate approximations over parameter ranges.

We begin with a few general facts about high-order function differentiation.

Fact 22 (Faá di Bruno formula [2]).

The $j^{\text{th}}$ derivative of a composite function $\xi(\eta(x))$ is given by:

\frac{{\mathrm{d}}^{j}}{{\mathrm{d}}x^{j}}\xi(\eta(x))=\sum_{\begin{subarray}{% c}k_{1},\dots,k_{j}\geq 0:\\ k_{1}+2k_{2}+\dots+jk_{j}=j\end{subarray}}\frac{j!}{k_{1}!k_{2}!\cdots k_{j}!}% \xi^{(k_{1}+k_{2}+\cdots+k_{j})}(\eta(x))\prod_{i=1}^{j}\left(\frac{\eta^{(i)}% (x)}{i!}\right)^{k_{i}},

Fact 23.

If $f(0)>0$ and all the derivatives of $g(x)=\log f(x)$ are non-negative at $0$ (we say that $f$ is log-absolutely monotonic at $0$ ), then all derivatives of $f(x)^{q}$ at $0$ are non-negative for any fixed $q\geq 0$ .

Proof.

Let $\xi(x):=e^{qx}$ . Note that $\xi^{(j)}(g(0))=q^{j}e^{qg(0)}=q^{j}f(0)^{q}>0$ for $j\geq 0$ . Given that $g^{(i)}(0)>0$ for all $i>0$ , the Faà di Bruno formula implies that all the derivatives of $\xi(g(x))=f(x)^{q}$ are non-negative. $\hfill\blacktriangleleft$

We now apply these facts to the Incomplete Beta function.

Lemma 24.

Let $x\in[0,1],\rho\in[0,1],q\geq 0$ . We have

I(x;\rho,1-\rho)^{q}=(\Gamma(1+\rho)\Gamma(1-\rho))^{-q}\sum_{j=0}^{\infty}G_{% j}(\rho,q)x^{\rho q+j}

for functions $G$ defined by

\displaystyle G_{j}(\rho,q)

\displaystyle=\sum_{\begin{subarray}{c}k_{1},\dots,k_{j}:\\ k_{1}+2k_{2}+\dots+jk_{j}=j\end{subarray}}\frac{(k_{1}+\dots+k_{j})!}{k_{1}!% \cdots k_{j}!}\binom{q}{k_{1}+\dots+k_{j}}\prod_{i=1}^{j}\Biggl(\frac{\rho}{% \rho+i}\binom{\rho+i-1}{i}\Biggr)^{k_{i}}

Each $G_{j}$ is a non-negative rational function of $\rho$ and $q$ .

Proof.

Let us consider the functions defined as follows:

f(x)=\frac{\rho\mathrm{B}(x;\rho,1-\rho)}{x^{\rho}},\quad\text{and}\quad g(x)=% x^{q}.

So the $q^{\text{th}}$ power of the Incomplete Beta function can be expressed by the composition of $g$ and $f$ :

I(x;\rho,1-\rho)^{q}=(\Gamma(1+\rho)\Gamma(1-\rho))^{-q}x^{\rho q}\cdot(g\circ f% )(x).

We have the series representation of $f(x)$ :

f(x)=\sum_{i=0}^{\infty}a_{i}x^{i},\qquad\text{for }a_{i}=\frac{\rho}{\rho+i}% \binom{\rho+i-1}{i}

The coefficients satisfy a log-convexity condition $\frac{a_{i}a_{i-2}}{a_{i-1}^{2}}=\frac{(i-1)(i+\rho-1)^{3}}{i(i+\rho-2)^{2}(i+% \rho)}\geq 1$ for $i\geq 2$ . By Lemma 30 we conclude that $f$ is log-absolutely monotonic. (See Appendix A for further details.) Consequently, by Fact 23 we deduce that all derivatives of $f$ are non-negative.

The explicit formula for the coefficients follows from the Faà di Bruno formula (Fact 22) coupled with elementary algebraic manipulations. Since $i,k_{1},\dots,k_{j}$ are non-negative integers, each term in the summation is a rational function of $q$ and $\rho$ . $\hfill\blacktriangleleft$

For reference, we list the first few values of $G_{j}$ :

G_{0}=1,\qquad G_{1}=\frac{q\rho^{2}}{1+\rho},\qquad G_{2}=\frac{q^{2}\rho^{5}% +2q^{2}\rho^{4}+q\rho^{4}+3q\rho^{3}+q\rho^{2}}{2(1+\rho)^{2}(2+\rho)}

Lemma 25.

Suppose we are given values $x_{1},x_{2},\rho_{1},\rho_{2}>0$ . For $i=1,2$ and $j\geq 0$ , define parameters

		$\displaystyle\theta_{i}$	$\displaystyle=(\Gamma(1+\rho_{i})\Gamma(1-\rho_{i}))^{1-1/x_{i}}$
		$\displaystyle\kappa_{i,j}$	$\displaystyle=\frac{\theta_{i}\rho_{i}}{jx_{i}+\rho_{i}}\binom{\rho_{i}/x_{i}+% j}{\rho_{i}}G_{j}(\rho_{i},1/x_{i}-1)$

and for $j_{1},j_{2}\geq 0$ define parameter

\alpha_{j_{1},j_{2}}=\binom{\rho_{1}(1/x_{1}-1)+\rho_{2}(1/x_{2}-1)+j_{1}+j_{2% }}{\rho_{1}(1/x_{1}-1)+j_{1}}^{-1}

Then

\Psi(x_{1},x_{2};\rho_{1},\rho_{2})=\sum_{j_{1}=0}^{\infty}\sum_{j_{2}=0}^{% \infty}\alpha_{j_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}

Proof.

Let $(X_{1},X_{2})\sim\text{Dir}(\rho_{1},\rho_{2};1-\rho_{1}-\rho_{2})$ , and for $i=1,2$ let $q_{i}=1/x_{i}-1$ and $Y_{i}=I(X_{i},\rho_{i},1-\rho_{i})$ . By Fact 5(5), we have

\mathbb{E}[X_{1}^{\beta_{1}}X_{2}^{\beta_{2}}]=\frac{\Gamma(\rho_{1}+\beta_{1}% )\Gamma(\rho_{2}+\beta_{2})}{\Gamma(1+\beta_{1}+\beta_{2})\Gamma(\rho_{1})% \Gamma(\rho_{2})}

for $\beta_{1},\beta_{2}\geq 0$ . In particular, with some algebraic manipulations, we have

\displaystyle\mathbb{E}[X_{i}^{\rho_{i}q_{i}+j}]

\displaystyle=\frac{\Gamma(q_{i}\rho_{i}+\rho_{i}+j)}{\Gamma(\rho_{i})\Gamma(q% _{i}\rho_{i}+j+1)}=\frac{\rho_{i}}{jx_{i}+\rho_{i}}\binom{\rho_{i}/x_{i}+j}{% \rho_{i}}=\frac{x_{i}\kappa_{i,j}}{\theta_{i}G_{j}(\rho_{i},q_{i})}

Likewise, we can calculate
$\displaystyle\frac{\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}X_{2}^{\rho_{2}q_{2}+% j_{2}}]}{\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}]\mathbb{E}[X_{2}^{\rho_{2}q_{2% }+j_{2}}]}=\frac{\Gamma(\rho_{1}q_{1}+j_{1}+1)\Gamma(\rho_{2}q_{2}+j_{2}+1)}{% \Gamma(\rho_{1}q_{1}+\rho_{2}q_{2}+j_{1}+j_{2}+1)}=\frac{1}{\binom{\rho_{1}q_{% 1}+\rho_{2}q_{2}+j_{1}+j_{2}}{\rho_{1}q_{1}+j_{1}}}=\alpha_{j_{1},j_{2}}.$

We can now expand the definition of $\Psi$ as:
$\displaystyle\Psi(x_{1},x_{2};\rho_{1},\rho_{2})=\frac{\mathbb{E}[Y_{1}^{q_{1}% }Y_{2}^{q_{2}}]}{x_{1}x_{2}}=\frac{\theta_{1}\theta_{2}}{x_{1}x_{2}}\sum_{j_{1% }=0}^{\infty}\sum_{j_{2}=0}^{\infty}G_{j_{1}}(\rho_{1},q_{1})G_{j_{2}}(\rho_{2% },q_{2})\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}X_{2}^{\rho_{2}q_{2}+j_{2}}]$ $\displaystyle\quad=\frac{\theta_{1}\theta_{2}}{x_{1}x_{2}}\sum_{j_{1}=0}^{% \infty}\sum_{j_{2}=0}^{\infty}G_{j_{1}}(\rho_{1},q_{1})G_{j_{2}}(\rho_{2},q_{2% })\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}]\mathbb{E}[X_{2}^{\rho_{2}q_{2}+j_{2}% }]\cdot\frac{\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}X_{2}^{\rho_{2}q_{2}+j_{2}}% ]}{\mathbb{E}[X_{1}^{\rho_{1}q_{1}+j_{1}}]\mathbb{E}[X_{2}^{\rho_{2}q_{2}+j_{2% }}]}$ $\displaystyle\quad=\frac{\theta_{1}\theta_{2}}{x_{1}x_{2}}\sum_{j_{1}=0}^{% \infty}\sum_{j_{2}=0}^{\infty}G_{j_{1}}(\rho_{1},q_{1})G_{j_{2}}(\rho_{2},q_{2% })\cdot\frac{x_{1}\kappa_{1,j_{1}}}{\theta_{1}G_{j_{1}}(\rho_{1},q_{1})}\cdot% \frac{x_{2}\kappa_{2,j_{2}}}{\theta_{2}G_{j_{2}}(\rho_{2},q_{2})}\cdot\alpha_{% j_{1},j_{2}}$ $\displaystyle\quad=\sum_{j_{1}\geq 0,j_{2}\geq 0}\alpha_{j_{1},j_{2}}\kappa_{1% ,j_{1}}\kappa_{2,j_{2}}.\$ $\hfill\blacktriangleleft$

Proposition 26.

For the decomposition of Lemma 25, we $\kappa_{i,j}\geq 0$ and $\sum_{j=0}^{\infty}\kappa_{i,j}=1$ for $i=1,2$ .

Proof.

The non-negativity of $\kappa_{i,j}$ follows from the fact that $G_{j}(\rho,q)\geq 0$ ; the remaining terms in the definition of $\kappa$ are clearly non-negative.

For the summation bound, by symmetry we consider just $i=1$ . Let $(X_{1},X_{2})\sim\text{Dir}(\rho_{1},\rho_{2};1-\rho_{1}-\rho_{2})$ , and $Y_{1}=I(X_{1};\rho_{1},1-\rho_{1})$ . Note that $Y_{1}$ has the marginal distribution of a uniform- $[0,1]$ random variable, so

\mathbb{E}[Y_{1}^{1/x_{1}-1}]=x_{1}.

Alternatively, via Lemma 25, we can write

\displaystyle\mathbb{E}[Y_{1}^{1/x_{1}-1}]

\displaystyle=\mathbb{E}[Y_{1}^{1/x_{1}-1}Y_{2}^{1/1-1}]=x_{1}\Psi(x_{1},1;% \rho_{1},\rho_{2})=x_{1}\sum_{j_{1}=0}^{\infty}\sum_{j_{2}=0}^{\infty}\alpha_{% j_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}

where $x_{2}=1$ .

Consider taking the limit as $\rho_{2}\rightarrow 0$ . Observe that $G_{j}(\rho,0)=0$ for $j>0$ , and $G_{0}(\rho,1)=1$ . So all the terms $j_{2}>0$ disappear from the sum in the limit. Furthermore, we have $\kappa_{2,0}=1$ and $\alpha_{j_{1},0}=1$ . So the sum approaches to $\sum_{j_{1}=0}^{\infty}\kappa_{1,j_{1}}$ . We have shown that

x_{1}=\mathbb{E}[Y_{1}^{1/x_{1}-1}]=x_{1}\Psi(x_{1},1;\rho_{1},\rho_{2})% \rightarrow x_{1}\sum_{j_{1}=0}^{\infty}\kappa_{1,j_{1}}.\

$\hfill\blacktriangleleft$

Lemma 27.

With the notation of Lemma 25, for any integers $k_{1},k_{2}\geq 0$ we have

	$\displaystyle\Psi(x_{1},x_{2};\rho_{1},\rho_{2})\leq\sum_{j_{1}<k_{1},j_{2}<k_% {2}}\bigl(\alpha_{j_{1},j_{2}}-\alpha_{j_{1},k_{2}}-\alpha_{k_{1},j_{2}}+% \alpha_{k_{1},k_{2}}\bigr)\kappa_{1,j_{1}}\kappa_{2,j_{2}}$
	$\displaystyle\qquad\qquad+\sum_{j_{1}<k_{1}}(\alpha_{j_{1},k_{2}}-\alpha_{k_{1% },k_{2}})\kappa_{1,j_{1}}+\sum_{j_{2}<k_{2}}(\alpha_{k_{1},j_{2}}-\alpha_{k_{1% },k_{2}})\kappa_{2,j_{2}}+\alpha_{k_{1},k_{2}}$

$\blacktriangleright$ Remark.

We refer to this as as the $(k_{1},k_{2})$ -order approximation of $\Psi$ . If $k_{1}=k_{2}=k$ , we refer to it simply as the $k^{\text{th}}$ -order approximation. Proposition 8 is simply the $0^{\text{th}}$ -order approximation.

Proof.

Note that $\alpha_{j_{1},j_{2}}$ is a decreasing function of $j_{1}$ as

\alpha_{j_{1}+1,j_{2}}/\alpha_{j_{1},j_{2}}=\frac{\rho_{1}q_{1}+j_{1}+1}{\rho_% {1}q_{1}+\rho_{2}q_{2}+j_{1}+j_{2}+1}\leq 1;

by a completely symmetric argument it is also a decreasing function of $j_{2}$ .

Using Lemma 25, non-negativity of $\kappa$ , and monotonicity of $\alpha_{j_{1},j_{2}}$ , we thus get
$\displaystyle\Psi(x_{1},x_{2};\rho_{1},\rho_{2})=\sum_{j_{1}\geq 0,j_{2}\geq 0% }\alpha_{j_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}$ $\displaystyle\quad\leq\sum_{\begin{subarray}{c}j_{1}<k_{1}\\ j_{2}<k_{2}\end{subarray}}\alpha_{j_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}% +\sum_{\begin{subarray}{c}j_{1}<k_{1}\\ j_{2}\geq k_{2}\end{subarray}}\alpha_{j_{1},k_{2}}\kappa_{1,j_{1}}\kappa_{2,j_% {2}}+\sum_{\begin{subarray}{c}j_{1}\geq k_{1}\\ j_{2}<k_{2}\end{subarray}}\alpha_{k_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}% +\sum_{\begin{subarray}{c}j_{1}\geq k_{1}\\ j_{2}\geq k_{2}\end{subarray}}\alpha_{k_{1},k_{2}}\kappa_{1,j_{1}}\kappa_{2,j_% {2}}$ $\displaystyle\quad=\sum_{\begin{subarray}{c}j_{1}<k_{1}\\ j_{2}<k_{2}\end{subarray}}\alpha_{j_{1},j_{2}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}% +\sum_{j_{1}<k_{1}}\alpha_{j_{1},k_{2}}\kappa_{1,j_{1}}\Bigl(1-\sum_{j_{2}<k_{% 2}}\kappa_{2,j_{2}}\Bigr)+\sum_{j_{2}<k_{2}}\alpha_{k_{1},j_{2}}\kappa_{2,j_{2% }}\Bigl(1-\sum_{j_{1}<k_{1}}\kappa_{1,j_{1}}\Bigr)$ $\displaystyle\qquad\qquad+\alpha_{k_{1},k_{2}}\Bigl(1-\sum_{j_{2}<k_{2}}\kappa% _{2,j_{2}}-\sum_{j_{1}<k_{1}}\kappa_{1,j_{1}}+\sum_{\begin{subarray}{c}j_{1}<k% _{1}\\ j_{2}<k_{2}\end{subarray}}\kappa_{1,j_{1}}\kappa_{2,j_{2}}\Bigr)$

where the final line uses $\sum_{j}\kappa_{i,j}=1$ . With some rearrangement of terms, this gives the claimed bound. $\hfill\blacktriangleleft$

Corollary 28.

Let $\lambda_{1},\lambda_{2}>0$ be fixed positive reals. For $x_{1},x_{2}>0$ , there holds

\lim_{x_{1},x_{2}\rightarrow 0}\Psi(x_{1},x_{2};\lambda_{1}x_{1},\lambda_{2}x_% {2})=\binom{\lambda_{1}+\lambda_{2}}{\lambda_{1}}^{-1}

Proof.

For an upper bound on the limit, apply Lemma 27 with $k_{i}=0,\rho_{i}=\lambda_{i}x_{i}$ ; note that $\alpha_{0,0}\rightarrow\binom{\lambda_{1}+\lambda_{2}}{\lambda_{1}}^{-1}$ as $x_{1},x_{2}\rightarrow 0$ . For the lower bound, Lemma 25 and the fact that the terms $\kappa,\alpha$ are non-negative gives $\Psi(x_{1},x_{2};\rho_{1},\rho_{2})\geq\alpha_{0,0}\kappa_{1,0}\kappa_{2,0}$ . It can be checked by routine calculations that $\kappa_{1,i}\rightarrow 1$ as $x_{i}\rightarrow 0$ . $\hfill\blacktriangleleft$

References

[1] Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms, 13(2):21:1–21:20, 2017. doi:10.1145/2928272.
[2] L. F. A. Arbogast. Du calcul des derivations. Levrault, Strasbourg, 1800. Entirely freely available from Google Books. URL: https://books.google.com/books?id=YoPq8uCy5Y8C.
[3] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson. Lift-and-round to improve weighted completion time on unrelated machines. SIAM Journal on Computing, 50(3):STOC16–138, 2019.
[4] F Barthe, F Gamboa, L Lozada-Chang, and A Rouault. Generalized Dirichlet distributions on the ball and moments. Alea, 7:319–340, 2010.
[5] Alok Baveja, Xiaoran Qu, and Aravind Srinivasan. Approximating weighted completion time via stronger negative correlation. Journal of Scheduling, 27(4):319–328, 2024. doi:10.1007/S10951-023-00780-Y.
[6] Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. Chapman & Hall/CRC, 2 edition, 2003.
[7] David G Harris. Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time. ACM Transactions on Algorithms, 2025.
[8] Sungjin Im and Shi Li. Improved approximations for unrelated machine scheduling. In Proc. 2023 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2917–2946, 2023. doi:10.1137/1.9781611977554.CH111.
[9] Sungjin Im and Maryam Shadloo. Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In Proc. 14th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2790–2809, 2020. doi:10.1137/1.9781611975994.170.
[10] Kumar Joag-dev and Frank Proschan. Negative association of random variables with applications. Annals of Statistics, 11:286–295, 1983. URL: https://api.semanticscholar.org/CorpusID:119668291.
[11] Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM Journal on Computing, 49(4):FOCS17–409, 2020. doi:10.1137/17M1156332.
[12] Shi Li. Approximating unrelated machine weighted completion time using iterative rounding and computer assisted proofs. In Proc. 2025 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 553–571, 2025. doi:10.1137/1.9781611978322.17.
[13] Joseph Naor, Aravind Srinivasan, and David Wajc. Online dependent rounding schemes for bipartite matchings, with applications. In Proc. 2025 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3116–3154, 2025.
[14] Wayne E Smith et al. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.

Appendix A Criterion for log-absolutely monotonic functions

We need to show that a function related to the Incomplete Beta function is log-absolutely monotonic. To do so, we will show a general criterion for functions with fast-growing derivatives. This may be of independent interest.

Lemma 29.

Let $k\geq 1$ , and let $f$ be $k$ -times differentiable in a neighborhood of $0$ , with $f(0)>0$ . Define $a_{i}=f^{(i)}(0)/i!$ for $j\geq 0$ , and let $g(x)=\log f(x)$ , with $c_{i}=g^{(i)}(0)/i!$ for $i\geq 1$ . Then

ka_{0}c_{k}=ka_{k}-\sum_{i=1}^{k-1}i\,a_{k-i}c_{i}.

(1)

Proof.

Since $f(x)=e^{g(x)}$ , we have $f^{\prime}(x)=g^{\prime}(x)f(x)$ . Differentiating $k-1$ times and applying the general Leibniz rule yields
$f^{(k)}(x)=(g^{\prime}\cdot f)^{(k-1)}(x)=\sum_{i=0}^{k-1}\binom{k-1}{i}\,g^{(% i+1)}(x)\,f^{(k-1-i)}(x)=\sum_{i=1}^{k}\binom{k-1}{i-1}\,g^{(i)}(x)\,f^{(k-i)}% (x).$

Evaluating at $x=0$ and using the definitions of $a_{k-i}$ and $c_{i}$ , we obtain

k!\,a_{k}=\sum_{i=1}^{k}\binom{k-1}{i-1}\,i!\,c_{i}\,(k-i)!\,a_{k-i}.

Dividing both sides by $(k-1)!$ gives

ka_{k}=\sum_{i=1}^{k}i\,c_{i}\,a_{k-i}.

Finally, isolating the $i=k$ term completes the proof. $\hfill\blacktriangleleft$

Lemma 30.

Let $f$ be an infinitely differentiable function defined in a neighborhood of zero, and let $a_{k}=f^{(k)}(0)/k!$ for each $k\geq 0$ . Define function $g(x)=\log f(x)$ and $c_{k}=g^{(k)}(x)/k!$ .

Suppose that the coefficients $a_{k}$ are positive and log-convex, i.e. $a_{k}a_{k-2}\geq a_{k-1}^{2}$ for all $k\geq 2$ . Then

\displaystyle kc_{k}\geq a_{k}+(k-1)\bigl(\frac{a_{k}}{a_{k-1}}-\frac{a_{1}}{a% _{0}}\bigr)c_{k-1}>0\qquad\text{for all $k\geq 1$}

(2)

In particular, $f$ is log-absolutely monotonic at $x=0$ .

Proof.

The log-convexity condition means that the ratios $a_{i}/a_{i-1}$ are nondecreasing in $i$ . By rescaling $f$ , we may assume without loss of generality that $f(0)=1$ , i.e. $a_{0}=1$ .

We show the claim by strong induction on $k$ . For a given value $k\geq 1$ , use Lemma 29 (with $a_{0}=1$ ) to calculate:

kc_{k}=ka_{k}-\sum_{i=1}^{k-1}ia_{k-i}c_{i}=ka_{k}-(k-1)a_{1}c_{k-1}-\sum_{i=1% }^{k-2}ia_{k-i}c_{i}

Note that $a_{k-i}/a_{k-1-i}\leq a_{k}/a_{k-1}$ by our assumption on the coefficients $a$ , and by our induction hypothesis we have $c_{i}\geq 0$ for $i=1,\ldots,k-2$ . So $a_{k-i}c_{i}\leq(a_{k}/a_{k-1})\cdot a_{k-1-i}c_{i}$ , and hence

\displaystyle kc_{k}

\displaystyle\geq ka_{k}-(k-1)a_{1}c_{k-1}-a_{k}/a_{k-1}\cdot\sum_{i=1}^{k-2}% ia_{k-1-i}c_{i}

Again using Lemma 29, we see that this is precisely
$\displaystyle ka_{k}-(k-1)a_{1}c_{k-1}-a_{k}/a_{k-1}\cdot(k-1)(a_{k-1}-c_{k-1}% )=a_{k}+(k-1)c_{k-1}(a_{k}/a_{k-1}-a_{1})$

This is positive, as $a_{k}$ , $a_{k}/a_{k-1}-a_{1}$ and $c_{k-1}$ are all positive. This completes the induction. $\hfill\blacktriangleleft$

Appendix B Derivation of function $𝑭$ in Algorithm 3

Here we give the motivation for the function $F$ . Let us suppose that all the edge demands $g_{e}$ are infinitesimal. We ignore all quadratic terms in $g$ , and just focus on the first-order terms. When we do this, we get

x_{e}\approx y_{e}\approx F(r_{e})g_{e},\qquad\rho_{e}\approx\alpha x_{e}

We will leave $F$ as a function to be determined, and $\alpha$ as a free parameter. As a starting point, these should satisfy the properties in Observation 12:

(a)

$F$ is nonnegative, increasing, and concave-up;
(b)

$\int_{t=0}^{1}F(t)\ \mathrm{d}t=1/\alpha$ ;
(c)

$F(1)=1$ .

(Note that, in Observation 12, $\alpha\int_{t=0}^{1}F(t)\mathrm{d}t$ and $F(1)$ are very slightly less than $1$ ; these are artifacts caused by our use of decimal values for the numerical constants.)

By Corollary 28 and Observation 16(c), we can approximate the $\Psi$ function for edges $e, f$ by:

\Psi(x_{e},x_{f};\rho_{e},\rho_{f})\approx\binom{2a}{a}^{-1}

where we again ignore all high-order terms. By the same argument as in Theorem 18, the probability that edge $e$ is matched is then at least

g_{e}F(r_{e})\Bigl(1-c\int_{t=0}^{r_{e}}F(t)\ \mathrm{d}t\Bigr)\qquad\text{for% constant $c=\binom{2\alpha}{\alpha}^{-1}$}.

Define $Q(r)=\int_{t=0}^{r}F(t)\ \mathrm{d}t$ , so the probability that $e$ is matched is $g_{e}Q^{\prime}(r_{e})(1-cQ(r_{e}))$ . We want an approximation ratio irrespective of $r_{e}$ ; hence, the quantity $Q^{\prime}(r_{e})(1-cQ(r_{e}))$ should not depend on $r_{e}$ :

\frac{\mathrm{d}}{\mathrm{d}t}Q^{\prime}(t)(1-cQ(t))=0

So we have a second-order differential equation

Q^{\prime\prime}(t)-c(Q^{\prime}(t))^{2}-cQ(t)Q^{\prime\prime}(t)=0

along with boundary conditions $Q(0)=0,Q^{\prime}(1)=1,Q^{\prime}(t)>0$ , which has the solution

Q(t)=\frac{1-\sqrt{1-t\bigl(2c\sqrt{c^{2}+1}-2c^{2}\bigr)}}{c}

(3)

where $c$ can be viewed as a function of parameter $\alpha$ .

At this point, we can choose $\alpha=1.2337$ in order to make $\alpha Q(1)$ slightly smaller than one. We can also replace the constant terms in Eq. (3), which are functions of $\alpha$ , with nearby numerical values to give $Q^{\prime}(1)<1$ and $Q(1)<1/\alpha$ . We finally define $F(t)=Q^{\prime}(t)$ .

Appendix C Proof of Lemma 10

1.

The random variables $T_{e}:e\in N(v)$ are generated independently, so $A_{e}:e\in N(v)$ are also independent. Since each $A_{e}$ is uniform, the inverse transform $Z_{e}=-\frac{\log A_{e}}{x_{e}}$ has exponential distribution of rate $x_{e}$ .
2.

Each variable $A_{e}$ is a monotone increasing function of $T_{e}$ , so the random variables $A_{e}:e\in E$ are NA [10].
3.

The random variables $(Z_{e})_{\{e\in N(v)\}}$ are independent exponentials of rate $x_{e}$ respectively. By the well-known properties of exponential random variables, $Q:=\frac{x(N(v))-x_{e}}{1-x_{e}}\min_{f\in N(v)\setminus\{e\}}Z_{f}$ is an exponential random variable with rate $1-x_{e}$ . So $\Pr[X_{e}=1]=\Pr[Z_{e}<Q]=\frac{x_{e}}{1+(1-x_{e})}=x_{e}$ .
4.

By hypothesis, we have $x(N(v))\leq 1$ . So if $X_{e}=1$ , then $Z_{e}<\frac{x(N(v))-x_{e}}{1-x_{e}}Z_{f}\leq Z_{f}$ for all other edges $f\in N(v)\setminus\{e\}$ ; clearly, there can be at most one edge with this property.
5.

Each term $A_{e}^{1/x_{e}-1}$ is an increasing nonnegative function of $A_{e}$ . As the random variables $A_{e}$ are NA, by [10], we have $\mathbb{E}\bigl[\prod_{e\in S}A_{e}^{1/x_{e}-1}\bigr]\leq\prod_{e\in S}\mathbb% {E}\bigl[A_{e}^{1/x_{e}-1}\bigr]$ . Since each $A_{e}$ is a uniform random variable, it satisfies $\mathbb{E}[A_{e}^{1/x_{e}-1}]=x_{e}$ . This shows the bound $\mathbb{E}\bigl[\prod_{e\in S}A_{e}^{1/x_{e}-1}\bigr]\leq\prod_{e\in S}x_{e}.$

For the second bound, we may assume that all the right-nodes of the edges in $S$ are distinct, as otherwise $\prod_{e\in S}X_{e}=0$ with probability one. Define $S^{\prime}$ to be the set of edges outside $S$ that share a right-node with an edge in $S$ , and let $W,W^{\prime}$ denote the set of left-nodes of edge-sets $S$ and $S^{\prime}$ respectively. We claim that $W,W^{\prime}$ are disjoint. For, suppose that $u\in W\cap W^{\prime}$ . So there are edges $(u,v)\in S,(u,v^{\prime})\in S^{\prime}$ ; by definition of $S^{\prime}$ , this implies that there is an edge $(u^{\prime},v^{\prime})\in S$ . Then the edges $(u^{\prime},v^{\prime}),(u,v)$ have distance two in the line graph of $G$ , contradicting that $S$ is stable.

Now suppose we condition on all random variables corresponding to the nodes in $W$ . In particular, this reveals all the random variables $A_{S}:=(A_{e}:e\in S)$ . The random variables corresponding to nodes in $W^{\prime}$ have their original unconditioned probability distributions.

Consider an edge $e=(u,v)\in S$ . Because we have assumed that edges in $S$ have distinct-right nodes, all edges $f\in N(v)\setminus\{e\}$ are in $S^{\prime}$ . All such random variables correspond to nodes in $W^{\prime}$ and retain their original, unconditioned probabilities distributions. In particular, the random variables $Z_{f}:f\in N(v)\setminus\{e\}$ are independent unit exponentials. So $Q:=\frac{x(N(v))-x_{e}}{1-x_{e}}\min_{f\in N(v)\setminus\{e\}}Z_{f}$ is an exponential random variable with rate $1-x_{e}$ , and hence

$\displaystyle\mathbb{E}[X_{e}\mid A_{S}]$ $\displaystyle=\Pr[Z_{e}<Q\;\big|\;A_{S}]=\mathrm{e}^{-(1-x_{e})Z_{e}}=A_{e}^{1% /x_{e}-1}.$

Since the random variables $A_{S^{\prime}}$ are NA, then by [10] we have

$\displaystyle\mathbb{E}\Bigl[\prod_{e\in S}X_{e}\mid A_{S}\Bigr]\leq\prod_{e% \in S}\mathbb{E}[X_{e}\mid A_{S}]=\prod_{e\in S}A_{e}^{1/x_{e}-1}$

To finish, we apply iterated expectations with respect to random variables $A_{S}$ .

[bib.bib1] [1] Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms, 13(2):21:1–21:20, 2017. doi:10.1145/2928272.

[bib.bib2] [2] L. F. A. Arbogast. Du calcul des derivations. Levrault, Strasbourg, 1800. Entirely freely available from Google Books. URL: https://books.google.com/books?id=YoPq8uCy5Y8C.

[bib.bib3] [3] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson. Lift-and-round to improve weighted completion time on unrelated machines. SIAM Journal on Computing, 50(3):STOC16–138, 2019.

[bib.bib4] [4] F Barthe, F Gamboa, L Lozada-Chang, and A Rouault. Generalized Dirichlet distributions on the ball and moments. Alea, 7:319–340, 2010.

[bib.bib5] [5] Alok Baveja, Xiaoran Qu, and Aravind Srinivasan. Approximating weighted completion time via stronger negative correlation. Journal of Scheduling, 27(4):319–328, 2024. doi:10.1007/S10951-023-00780-Y.

[bib.bib6] [6] Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. Chapman & Hall/CRC, 2 edition, 2003.

[bib.bib7] [7] David G Harris. Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time. ACM Transactions on Algorithms, 2025.

[bib.bib8] [8] Sungjin Im and Shi Li. Improved approximations for unrelated machine scheduling. In Proc. 2023 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2917–2946, 2023. doi:10.1137/1.9781611977554.CH111.

[bib.bib9] [9] Sungjin Im and Maryam Shadloo. Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In Proc. 14th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2790–2809, 2020. doi:10.1137/1.9781611975994.170.

[bib.bib10] [10] Kumar Joag-dev and Frank Proschan. Negative association of random variables with applications. Annals of Statistics, 11:286–295, 1983. URL: https://api.semanticscholar.org/CorpusID:119668291.

[bib.bib11] [11] Shi Li. Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM Journal on Computing, 49(4):FOCS17–409, 2020. doi:10.1137/17M1156332.

[bib.bib12] [12] Shi Li. Approximating unrelated machine weighted completion time using iterative rounding and computer assisted proofs. In Proc. 2025 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 553–571, 2025. doi:10.1137/1.9781611978322.17.

[bib.bib13] [13] Joseph Naor, Aravind Srinivasan, and David Wajc. Online dependent rounding schemes for bipartite matchings, with applications. In Proc. 2025 annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3116–3154, 2025.

[bib.bib14] [14] Wayne E Smith et al. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.

	$\displaystyle Z^{\left(i^{},j^{}\right)}$	$\displaystyle=\frac{1}{2}\left(\sum_{j=1}^{j^{}}X_{j}^{\left(i^{}\right)}% \left(p_{j}^{\left(i^{}\right)}\right)^{2}+\sum_{j=1}^{j^{}}\sum_{j^{\prime}% =1}^{j^{}}X_{j}^{\left(i^{}\right)}X_{j^{\prime}}^{\left(i^{}\right)}p_{j}^% {\left(i^{}\right)}p_{j^{\prime}}^{\left(i^{*}\right)}\right)$
	$\displaystyle\mathrm{LB}^{\left(i^{},j^{}\right)}$	$\displaystyle=\frac{1}{2}\left(\sum_{j=1}^{j^{}}x_{j}^{\left(i^{}\right)}% \left(p_{j}^{\left(i^{}\right)}\right)^{2}+\sum_{j=1}^{j^{}}\sum_{j^{\prime}% =1}^{j^{}}x_{j,j^{\prime}}^{\left(i^{}\right)}p_{j}^{\left(i^{}\right)}p_{j% ^{\prime}}^{\left(i^{}\right)}\right)$

The Dirichlet Mechanism for Rounding with Strong Negative Correlation, with Applications

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Contributions

Theorem 1 (Simplified).

1.2 Application: Oblivious Online Matching

Theorem 2.

1.3 Application: Weighted Completion Time

2 Preliminaries

Definition 3 (Dirichlet distribution).

Definition 4 (Negatively Associated random variables).

Fact 5 (Properties of the Dirichlet distribution).

3 The Dirichlet mechanism

3.1 The Dirichlet copula

Observation 6.

Proof.

Proposition 7.

Proof.

Proposition 8.

3.2 Bipartite rounding

Definition 9 (Stable edge set).

Lemma 10 ([7]).

Proof.

Theorem 11.

Proof.

4 Online Matching algorithm

Observation 12.

Proposition 13.

Proof.

Proposition 14.

Proof.

Lemma 15.

Proof.

Observation 16.

Lemma 17.

Theorem 18.

Proof.

5 Weighted completion time on unrelated machines

Theorem 19 ([3]).

Proposition 20.

Proof.

Theorem† 21.

6 Analysis of the function 𝚿

Fact 22 (Faá di Bruno formula [2]).

Fact 23.

Proof.

Lemma 24.

Proof.

Lemma 25.

Proof.

Proposition 26.

Proof.

Lemma 27.

▶ Remark.

Proof.

Corollary 28.

Proof.

References

Appendix A Criterion for log-absolutely monotonic functions

Lemma 29.

Proof.

Lemma 30.

Proof.

Appendix B Derivation of function 𝑭 in Algorithm 3

Appendix C Proof of Lemma 10

Theorem^† 21.

6 Analysis of the function $\Psi$

$\blacktriangleright$ Remark.

Appendix B Derivation of function $𝑭$ in Algorithm 3