$3.415$-Approximation for Coflow Scheduling via Iterated Rounding

We present the first polynomial time algorithm which achieves a better than $4$-approximation for Coflow Scheduling without release dates and the first algorithm which achieves a better than $5$-approximation with release dates. More specifically, we show the following theorems.

Using a more technical construction, the guarantee of Theorem 1 can be slightly improved, details can be found in the full version. We additionally prove that in a certain asymptotic setting, roughly when most coflows have large finishing times in any optimum solution, we can achieve a $(2+ϵ)$-approximation, which is optimal. This result holds even in the case with release dates.

Note that using a framework by Khuller et al. [17], any improvement in the approximation ratio for Coflow Scheduling without release dates directly gives an improvement for the best known approximation for the online setting of Coflow Scheduling. The following table provides an overview over the state of the art of approximation algorithms for various variants of Coflow Scheduling and our respective improvements.

The main technical contributions are a novel allocation and rounding scheme for the individual edges of each coflow, inspired by techniques used in proving the Beck-Fiala Theorem from discrepancy theory and a framework for establishing the approximation ratio for combinations of several such edge scheduling algorithms.
Our algorithm follows a two phase approach. This has been done either implicitly or explicitly in most approaches found in the literature. In the first phase, for each coflow and its associated flows, deadlines are determined through an LP based approach combined with a randomized rounding procedure. These deadlines are equipped with a special structure which we exploit in the algorithm. They specifically provide a $2$-approximation cost guarantee with respect to some optimum solution. In the second phase, the goal is to find a valid allocation for the coflows, or more precisely for the individual edges of each coflow, to time-slots. In previous works, this was achieved by a simple greedy allocation procedure, which in the case without release dates achieves a deadline violation of at most a factor $2$ for each coflow, yielding a $4$-approximation. We use a combination of two algorithms, both the greedy allocation rule and a novel iterated rounding scheme. The greedy allocation performs well for small deadlines, but converges to a $2$-approximation for larger deadlines, while the rounding procedure can schedule large deadlines arbitrarily well, but has worse results for small ones. Note that these factors only capture the completion time delay and do not take into account the additional loss of factor $2$ from the deadline construction. By running both algorithms and picking the better result, we are able to improve upon the factor $4$.
To show the improved approximation ratio, we establish a general framework which can be used to bound the coflow scheduling approximation ratio for any collection of edge allocation algorithms.

The next chapter introduces important notation and discusses results from LP and graph theory which form an integral part of several subroutines. Section 3 provides a complete overview of the entire algorithm and the most important theorems for Coflow Scheduling without release dates. Full proofs and additional details can be found in the following Section 4. The extension to release dates is described in Section 5. Section 6 proves the $2+ϵ$ guarantee in the asymptotic case. The full version of this paper contains additional details and discusses some further related theory, such as results regarding the structure and complexity of the used LP, extending the algorithm to high edge multiplicities, the improved LP integrality gap, and shows how to achieve a slight improvement over the approximation guarantee from Theorem 7.

Given some coflow instance, we aim to determine a deadline for each of its coflows. These deadlines might not necessarily be strict in the sense that constructed schedules have to adhere to them, but they are rather used to both guide edge allocation procedures and to then bound their resulting costs. Most existing coflow approximation algorithms use a similar strategy.
We take a structural approach, where we first define structure which we want our deadlines to obey and then describe how such deadlines can be found. We capture the structural constraints in the following LP. It has been implicitly used in analysis by [14, 9] and others. Let $C_1\le C_2\le \mathrm{\dots }\le C_n$ be deadlines for the coflows and for easier notation define $C_0:=0$.

Instead of enforcing the necessary constraints for Coflow Scheduling for each individual time slot, LP I groups the slots into blocks in between the coflow deadlines. The variable $x_{s,e}$ describes the assignment of edge $e$ to block $s$. Constraint $(I)$ ensures that every edge from every coflow is fully scheduled. The block between $C_{s-1}$ and $C_s$ has size $C_s-C_{s-1}$, so constraint $(II)$ ensures that in every such block for every vertex the amount of adjacent edges does not exceed the block size. Constraint $(III)$ forces edges to be zero for blocks after the respective deadline. The step from individual time slot degree bounds to block degree bounds is justified by Kőnig’s Theorem (Theorem 4), as it guarantees that any bipartite graph with some maximum degree $\mathrm{\Delta }$ can be decomposed into $\mathrm{\Delta }$ matchings. This is equivalent to saying that any set of bipartite edges $E$ for which the induced graph has maximum degree $\mathrm{\Delta }$ can be scheduled in $\mathrm{\Delta }$ time slots.

Assuming the deadlines $C_1\le C_2\le \mathrm{\dots }\le C_n$ are set as the coflow finishing times from some optimal schedule for the underlying coflow instance, the edge assignment directly induces a feasible point inside LP I. For each edge $e$ which is scheduled in some time slot $t$ in the optimal schedule, set $x_{s,e}:=1$, for $s$ such that $t\in (C_{s-1},C_s]$. Set all other variables to $0$. As by definition of a valid solution, each edge is scheduled before its coflow’s deadline, constraint $(I)$ is fulfilled and constraint $(III)$ cannot be violated. As the edges in each time slot form a matching, constraint $(II)$ is also fulfilled.

Conversely, an integral solution to the LP corresponds to a valid solution for Coflow Scheduling. However, in order to be able to solve the LP in polynomial time, we cannot enforce integrality. Hence the constraints only enforce that the variable assignment corresponds to a fractional matching. There are instances and deadlines for which LP I is feasible, but no feasible integral point and therefore also no feasible integral schedule exists. In fact, determining whether an integral points exists is an $\mathbb{N}\mathbb{P}$-hard problem, for details we refer to the full version.

Finding some set of deadlines for which LP I is feasible is easy, as one can simply choose large enough values to guarantee feasibility. However, for the purpose of constructing good approximation algorithms for Coflow Scheduling, we require that the deadlines fulfill some cost guarantees with respect to an optimal coflow schedule.
There is an LP based approach which returns deadlines for which LP I is feasible and certain strong guarantees hold. This technique has been used by [14, 9] and others. They use a randomized rounding scheme on another LP formulation to determine integral deadlines $C_1^{\prime },\mathrm{\dots },C_n^{\prime }$. We slightly modify their algorithm and leave out the final step in which they round up the deadlines and obtain $C_1,\mathrm{\dots },C_n$. These deadlines are thus potentially fractional. By slightly modifying their proof, the following bound can be shown.

More details about the procedure used by [14] to determine such deadlines can be found in the full version. They only implicitly work with LP I, so we provide additional details on the connection. Note that the procedure can be de-randomized to obtain a fully deterministic algorithm.

The multiplicative factor of $2$ in Lemma 5 is optimal assuming $\mathbb{P}\ne \mathbb{N}\mathbb{P}$. This follows from the factor $(2-ϵ)$-approximation hardness of Concurrent Open Shop Scheduling, as Coflow Scheduling can be seen as a generalization of this problem [23].

Let $C_1,\mathrm{\dots },C_n$ be deadlines for which LP I is feasible and Lemma 5 holds. Using the result of the lemma, we immediately obtain that if we are able to find an allocation such that all edges from each coflow are scheduled by their respective deadlines, we have achieved a $2$-approximation for Coflow Scheduling. In the same way, if for some $\alpha \ge 1$ we are able to schedule each coflow $j$ by time $\alpha \cdot C_j$, we obtain a $2\cdot \alpha$ approximation algorithm.

We analyze two edge allocation algorithms which provide different guarantees for the finishing times of the coflows. The first algorithm $\mathrm{Greedy}$ is a simple greedy allocation scheme. This procedure was used by previous authors to derive $4$-approximation algorithms for Coflow Scheduling. Let $\mathrm{Greedy}(C_j)$ denote the finishing time of coflow $E_j$ in the schedule produced by $\mathrm{Greedy}$.

The second algorithm ${\mathrm{CBF}}^{\tau }$ is a novel allocation scheme using a form of iterated rounding inspired by the Beck-Fiala Theorem from discrepancy theory [4]. The algorithm is parameterized by $\tau \in {\mathbb{N}}_{\ge 2}$ and allocates the coflow deadlines to blocks, where each block’s size is some integer multiple of $\tau$. An edge assignment is then determined which only slightly violates the size of each block. This leads to the following completion time guarantees.

Note that the approximation guarantees of both algorithms are quite different. $\mathrm{Greedy}$ achieves rather strong approximation for small deadlines, while for large deadlines, through an appropriate choice of $\tau$, ${\mathrm{CBF}}^{\tau }$ gives good guarantees. In fact, under certain assumptions on the provided deadlines, ${\mathrm{CBF}}^{\tau }$ can achieve approximations arbitrarily close to the optimum of $1$, see Section 6.

Our coflow algorithm aims to achieve guarantees for both small and large deadlines by combining both algorithms in some way. The procedure is straightfoward. It obtains the deadlines $C_1,..,C_n$ through the procedure explained in Section 3.1 and then runs both $\mathrm{Greedy}$ and ${\mathrm{CBF}}^6$ independently, returning the schedule with lower cost. Analyzing the cost of the returned solution requires some care, as we need a uniform bound over any possible input instance.

By the definition of the coflow algorithm, for each possible instance $ℐ$, its cost $C_{\mathrm{ALG}}(ℐ)$ is given as the minimum of the costs $C_G(ℐ)$ and $C_{\mathrm{CBF}}(ℐ)$ of the $\mathrm{Greedy}$ and respectively ${\mathrm{CBF}}^6$ algorithm.
We show a general proof framework for such algorithms which provide deadline guarantees, which gives sharp bounds for taking minimums over several algorithms’ costs. The derivation is not difficult, but the framework offers a surprisingly simple and strong method to establish bounds for large classes of algorithms. It only requires bounds for the delay guarantees of the algorithms, which are usually relatively simple to establish.
For this purpose, let $C_1,\mathrm{\dots },C_n$ be deadlines for which LP I is feasible and let ${\mathrm{ALG}}_1,\mathrm{\dots },{\mathrm{ALG}}_k$ be algorithms producing valid coflow schedules from such deadlines, with ${\mathrm{ALG}}_i(C_j)$ being the finishing time of coflow $E_j$ in the schedule produced by ${\mathrm{ALG}}_i$. For $j\in [k]$, let $f_j$ be a function capturing a bound on the maximum weighted deadline delay of ${\mathrm{ALG}}_j$. This means that $f_j$ is such that ${\sum }_{j\in [n]}{\omega }_j\cdot {\mathrm{ALG}}_j(C_j)\le {\sum }_{j\in [n]}{\omega }_j\cdot f_j(C_j)$. Such functions might stem from bounds on individual deadlines like in the case of $\mathrm{Greedy}$, but can also come from bounds which are already given as a weighted sum over all deadlines like for ${\mathrm{CBF}}^{\tau }$.

Using the previous lemmata and theorems, we prove Theorem 1. The proof follows by application of the framework from Lemma 8 to selected edge allocation algorithms.

See 1

We start by introducing and analyzing a greedy allocation algorithm $\mathrm{Greedy}$, which is one of the edge allocation procedures used in previous works to achieve a $4$-approximation. Let $C_1\le C_2\le \mathrm{\cdots }\le C_n$ be deadlines for which LP I is feasible. $\mathrm{Greedy}$ schedules all coflows consecutively, starting with $E_1$ up to $E_n$. Each edge is simply scheduled in a work-conserving way, meaning that it is scheduled in the earliest possible time-slot in which both its vertices are free. By doing this for all edges, a schedule is obtained. For $j\in [n]$, let $\mathrm{Greedy}(C_j)$ be the finishing time of coflow $E_j$ in the schedule obtained from this procedure.

See 6

This section gives a proof of Theorem 7. We start by providing a full description of the algorithm, then we give a preliminary analysis and subsequently strengthen the guarantee through further refinements.

Like in the case of no release dates, we want to obtain deadlines for the coflows which obey some structural constraints. LP I does not contain release dates, but with some minor modifications we obtain a suitable LP. For this purpose, for some $\kappa \in [2n]$, define a sequence $D_1\le D_2\le \mathrm{\dots }\le D_{\kappa }$ containing exactly all deadlines and release dates. For some edge $e\in E$, let $r(e)$ be the index of the release date associated to $e$ in the chain of points in $D$ and respectively $d(e)$ the index of the deadline. Then we construct the following LP.

The structure of LP $R$ is very similar to LP I, just with added block separators for each release date and modification of the constraints to prevent edges from being scheduled in blocks before their respective release dates.

The same procedure by [14] used in Section 3.1 can be employed to obtain deadlines $C_1,\mathrm{\dots },C_n$ for which LP $R$ is feasible and for which the same cost bound from Lemma 5 holds.

Given such a set of deadlines for which LP $R$ is feasible, we again describe two algorithms ${\mathrm{Greedy}}_R$ and ${\mathrm{CBF}}_R^{\tau }$ which provide feasible allocations for all edges. Their guarantees are slightly worse due to the added release date constraints.
Like previously, ${\mathrm{Greedy}}_R(C_j)$ and ${\mathrm{CBF}}_R^{\tau }(C_j)$ will be used to denote the finishing time of coflow $E_j$ in the schedule provided by the respective algorithm.

The algorithm for Coflow Scheduling with release dates again works by obtaining deadlines and then running several edge allocation algorithms on these and returning the cheapest solution among them. To bound the cost, a framework very similar to the one described in Lemma 8 is used, though an additional bound on the distance to the optimum cost is needed due to the presence of the $r_j$ summand in the guarantee provided by ${\mathrm{Greedy}}_R$. As in any optimal solution the finishing time ${\mathrm{OPT}}_j$ of coflow $E_j$ has to be after $r_j$, we have $r_j\le {\mathrm{OPT}}_j-1$.

In the following lemma, like in Lemma 8, let $f_1,\mathrm{\dots },f_k$ be some functions capturing the edge allocation guarantees provided by some collection of algorithms ${\mathrm{ALG}}_1,\mathrm{\dots },{\mathrm{ALG}}_k$. In this case the functions additionally depend on a parameter $r_j\in {ℝ}_{\ge 0}$, which like in the case for $\mathrm{Greedy}$ captures the dependency on release dates.