Weighted Chairman Assignment and Flow-Time Scheduling

Let $m,n$ be positive integers. We say that a matrix $x\in {[0,1]}^{m\times n}$ is a fractional assignment if ${\sum }_{i\in [m]}{x}_{ij}=1$ for every column $j\in [n]$, and that $y\in {\{0,1\}}^{m\times n}$ is an (integral) assignment if ${\sum }_{i\in [m]}{y}_{ij}=1$ for every $j\in [n]$. Consider the following problem introduced by Niederreiter in 1972 [24, 25]: find the minimum value of $\mathrm{\Delta }(m)$ such that for every positive integer $n$ and fractional assignment $x\in {[0,1]}^{m\times n}$, there is an assignment $y\in {\{0,1\}}^{m\times n}$ so that for every row $i\in [m]$ and column $t\in [n]$,

This is known as the chairman assignment problem due to Tijdeman [27]: suppose $m$ states form a union and each state $i$ receives a value $x_{ij}$ from being a member at year $j$ so that ${\sum }_{i\in [m]}{x}_{ij}=1$. Every year a union chairman has to be selected in such a way that at any year $t$ the accumulated number of chairmen ${\sum }_{j\in [t]}{y}_{ij}$ from each state $i$ is proportional to its accumulated value ${\sum }_{j\in [t]}{x}_{ij}$. Niederreiter showed a bound of $\mathrm{\Delta }(m)\le m-1$ [24] which was subsequently improved by Meijer and Niederreiter to $\mathrm{\Delta }(m)\le O(\log m)$ [22] and by Tijdeman to $\mathrm{\Delta }(m)\le 1$ [26], who also showed that, for $m>1$ and any $\delta >0$, $\mathrm{\Delta }(m)\ge 1-\frac{1}{2m-2}-\delta$ via a family of examples with $n=\mathrm{\Omega }(1/\delta )$. The approaches of [22] and [26] are both based on an application of Hall’s theorem to a carefully constructed bipartite graph. Finally, Meijer matched this lower bound by showing $\mathrm{\Delta }(m)\le 1-\frac{1}{2m-2}$ [21]. Since then, there have been other proofs of this result through different approaches [27, 3, 16, 8]; see also the survey of Tijdeman [28].

We study the weighted chairman assignment problem where each $j\in [n]$ has an associated weight $d_j>0$ and we want to bound $|{\sum }_{j\in [t]}{d}_j(x_{ij}-y_{ij})|$ for every $i\in [m]$ and $t\in [n]$. All of the previous approaches in the unweighted setting rely on the fact that the increments to the integral assignment are integers and do not directly generalize to the weighted setting. Our main theorem generalizes an algorithm of Tijdeman [27] (see also Angel, Holroyd, Martin and Propp [3]) with a new analysis to show the following:

The weighted chairman assignment problem gains renewed interest due to a conjecture by Morell and Skutella [23]: given a flow $x$ from a single source to multiple sinks with varying demands, there is an unsplittable flow $y$ where each sink should be served by a single path, such that the discrepancy between the two flows on each arc is at most the maximum demand. The weighted chairman assignment problem with weights $d_1,\mathrm{\dots },d_n$ can be modeled as a single-source unsplittable flow instance with demands $d_1,\mathrm{\dots },d_n$ (see Section 2), and therefore Theorem 1 with discrepancy bound ${\max }_{j\in [n]}{d}_j$ would follow if the conjecture were true. When the demands are uniform, i.e., $d_1=\mathrm{\dots }=d_n=1$, the conjecture is true because by adding capacity constraints $\lfloor x\rfloor \le y\le \lceil x\rceil$ to the flow polytope we can find an integral flow $y$ which is automatically unsplittable and satisfies ${|x-y|}_1\le 1$. Therefore, the discrepancy bound $1$ for the (unweighted) chairman assignment follows as a consequence. The weighted setting corresponds to nonuniform demands, where so far all linear programming techniques fall apart.

As an application, we consider the following scheduling problem. Suppose there are $m$ machines $M$ and $n$ jobs $J$. Each machine $i\in M$ has a closing time $b_i\ge 0$. Each job $j\in J$ has a release time $r_j\ge 0$ and a processing time $d_j\ge 0$. Job $j$ can be scheduled on machine $i$ if and only if $r_j\le b_i$. The flow-time of a job $j$ is defined as the time elapsed from its release to completion. The goal is to schedule jobs to machines to minimize the maximum flow-time of any job. This is a special case of the restricted assignment variant of maximum flow-time minimization, where each job $j$ has a subset of machines $M_j\subseteq M$ that it can be scheduled on. In the most general form of the problem, each job $j$ has a potentially different processing time $d_{ij}$ on machines $i\in [m]$. Bansal, Rohwedder and Svensson [6] proved that a natural linear programming relaxation has integrality gap $O(\sqrt{\log n})$, and conjectured that an $O(1)$-approximation should be possible. We confirm this conjecture for the setting of machine closing times:

Previously, a $(3-\frac{2}{m})$-approximation was known via a greedy algorithm (first-in-first-out, or FIFO) for the setting of identical machines where $b_i=\mathrm{\infty }$ for all $i\in M$ [7, 20], and this bound is known to be tight for FIFO [19]. We also show that FIFO has approximation ratio at least $\mathrm{\Omega }(\log m)$ for the setting of closing times.

Furthermore, we give several lower bound constructions. We provide a construction simpler than Tijdeman’s [26] to establish a matching lower bound for the chairman assignment problem:

The assignment given in [26] that achieves $\mathrm{\Delta }(m)\le 1$ yields a strict inequality and has the property that $y_{ij}=0$ whenever $x_{ij}=0$. We give a construction showing that Tijdeman’s bound is tight under this additional constraint:

Finally, we disprove a conjecture in [3] that one may obtain a bound of 1 for all intervals, not just prefixes:

In particular, this implies that we cannot hope to directly apply our rounding approach to obtain a 2-approximation for maximum flow-time minimization.

Theorem 1 resolves a special case of a conjecture of Morell and Skutella [23] which can be formally stated as follows. Let $D=(V,A)$ be a directed acyclic graph with source $s\in V$, sink terminals $t_1,\mathrm{\dots },t_n\in V$ and associated demands $d\in {ℝ}_{>0}^n$. We say a flow $x\in {ℝ}_{\ge 0}^A$ satisfies the demands if $x({\delta }^{-}(t_j))=d_j$ for every $j\in [n]$, and $x({\delta }^{-}(v))=x({\delta }^{+}(v))$ for every $v\in V\setminus \{s,t_1,\mathrm{\dots },t_n\}$. We say a flow $y\in {ℝ}_{\ge 0}^A$ is unsplittable if for each $j\in [n]$ there is a single path $P_j$ from $s$ to $t_j$ that carries $d_j$ units of flow, so that $y_a={\sum }_{j:a\in P_j}{d}_j$ for every $a\in A$. Morell and Skutella conjectured the following:

They also showed the one-sided bound $x_a-y_a\le {\max }_{j\in [n]}{d}_j$ for all $a\in A$ may be satisfied, thereby complementing the previously known one-sided bound $y_a-x_a\le {\max }_{j\in [n]}{d}_j$ for all $a\in A$ of Dinitz, Garg and Goemans [12]. So far, Conjecture 6 has been established when the demands have the property that one divides another, i.e., $d_1\mid d_2\mid \mathrm{\dots }\mid d_n$ [23] and for special digraphs such as acyclic planar digraphs [29]; see also [2] for stronger guarantees for series-parallel digraphs.

To see the connection with Theorem 1, note that given positive integers $m,n$ we may construct a directed acyclic graph consisting of $m$ paths of length $n$ starting from $s$, with edges pointing at $n$ terminals along the way. Then any fractional assignment $x\in {[0,1]}^{m\times n}$ and weights $d\in {ℝ}_{>0}^n$ induce a flow so that each terminal $t_j$ has demand $d_j$ and each prefix is captured by one of the arcs in a path, as illustrated in Figure 1. An unsplittable flow routes each demand $d_j$ to $t_j$ through a path $i\in [m]$, which corresponds to assigning $j$ to $i$. Assuming Conjecture 6, such an assignment $y$ satisfies $|{\sum }_{j\in [t]}{d}_j(x_{ij}-y_{ij})|\le {\max }_{j\in [n]}{d}_j$ for all $i\in [m],t\in [n]$.

A variant of the chairman assignment problem is the carpooling problem [14, 1], where $j\in [n]$ can be assigned to $i\in [m]$ if and only if $x_{ij}\ne 0$. The weighted carpooling problem, which remains open, can also be viewed as a special case of Conjecture 6 using a similar construction that connects terminal $t_j$ to paths $i$ for which $x_{ij}\ne 0$:

Morell and Skutella [23] outlined the connection to maximum flow-time minimization and noted that Conjecture 7 would imply a 3-approximation for the restricted assignment setting. The best known approximation in polynomial time is $O(\log n)$ due to Bansal and Kulkarni via iterated rounding [5]. Bansal, Rohwedder and Svensson [6] prove a bound of $O(\sqrt{\log n})\cdot {\max }_{j\in [n]}{d}_j$ for Conjecture 7, leveraging a non-constructive argument from convex geometry by Banaszczyk [4], thereby showing that the natural linear programming relaxation for maximum flow-time minimization has integrality gap $O(\sqrt{\log n})$. For identical machines, a simple 3-approximation is known [7, 20]: sort the jobs by release times and assign them one by one to the machine with the least remaining processing time of jobs that have been assigned to it. The special case where release times are all zero corresponds to makespan minimization; the work of Lenstra, Shmoys and Tardos gives a 2-approximation algorithm via rounding [18]. Their approach also solves the Morell-Skutella conjecture for digraphs of diameter 2.

To the best of our knowledge, the weighted chairman assignment problem has not been studied before. The more general weighted carpooling problem fits within the broader framework of prefix discrepancy [6], and it is possible to derive a bound of $2m\cdot {\max }_{j\in [n]}{d}_j$ for Conjecture 7 via a linear algebraic argument [10, 9]. Together with Banaszczyk’s result [4], the current best bound for Conjecture 7 is $\min \{2m,O(\sqrt{\log n})\}\cdot {\max }_{j\in [n]}{d}_j$. The special case of Conjecture 7 where each column ${\{x_{ij}\}}_{i\in [m]}$ has at most two nonzero entries is known as the 2-sparse prefix Beck-Fiala problem and is equivalent to the general case up to a constant [6]. Proposition 4 shows that unlike Theorem 1, we cannot hope for a $(1-\delta )\cdot {\max }_{j\in [n]}{d}_j$ bound for Conjecture 7 for any $\delta >0$ even for $m=3$.

For the online version of the chairman assignment problem, where columns of $x$ arrive one at a time and the assignment must be decided irrevocably, it is known that the best possible bound is ${\sum }_{j=2}^m\frac{1}{j}=\mathrm{\Theta }(\log m)$ for adaptive adversaries, attainable with a simple greedy algorithm [11], and the analysis readily generalizes for the weighted setting. On the other hand, the best possible bound independent of $n$ for the online version of the carpooling problem is $\frac{m-1}{2}$ [11]. For the online 2-sparse prefix Beck-Fiala problem, there is also an $O(\sqrt{\log n})$ bound [17] and a $\mathrm{\Omega }(\sqrt[3]{\log n})$ lower bound [1] for oblivious adversaries. A recent line of work studies the online carpooling problem with recourse [15, 13], and it remains open to obtain a constant bound for the online chairman assignment problem with polylogarithmic recourse.

Given $m,n\in \mathbb{N}$ with $m>1$, denote $\epsilon :=\frac{1}{2m-2}$. Let $x\in {[0,1]}^{m\times n}$ be a fractional assignment. We normalize $d\in {ℝ}_{>0}^n$ so that ${\max }_{j\in [n]}{d}_j=1$, thereby assuming $d\in {(0,1]}^n$. For $j\in [n]$, denote by $s_j\in [m]$ the element to which $j$ will be assigned, so that $y_{ij}=1$ if $s_j=i$ and $0$ otherwise. For each $i\in [m]$ and $t\in [n]$, denote

At time $t$, the deadline of $i$ is defined as

which is set to $\mathrm{\infty }$ (or $n+1$) if such $T$ does not exist.

The set of candidates at time $t$ is defined as

At time $t$, the algorithm chooses a candidate with the earliest deadline. The detailed description is in Algorithm 1. We remark that if we only wanted a bound of ${\max }_{j\in [n]}{d}_j$ in Theorem 1, simpler definitions of deadline and candidates where setting $\epsilon =0$ in both definitions would have been sufficient.

The feasibility of the algorithm follows from the lemma below.

Let $M=[m]$ be a set of machines, and $J=[n]$ be a set of jobs. Each job $j\in J$ can be scheduled on a subset of machines $M_j\subseteq M$. Each job $j\in [n]$ has a processing time $d_j$ and release time $r_j$. Let $C_j$ be the completion time of $j$. Order the jobs by their release times $r_1\le r_2\le \mathrm{\cdots }\le r_n$. We want to schedule each job to a machine such that the maximum flow-time ${\max }_{j\in [n]}(C_j-r_j)$ is minimized. Consider the following linear programming relaxation for this problem:

Morell and Skutella [23] show that Conjecture 7 would imply the integrality gap of (3) is at most $3$. Efficiently computing such an assignment $y$ would lead to a $3$-approximation algorithm for maximum flow-time scheduling. It follows readily from their proof that upper-bounding ${\sum }_{j=s}^t{d}_j(y_{ij}-x_{ij})$ for every machine $i$ and interval of jobs defined by $1\le s\le t\le n$ suffices to prove the desired approximation ratio. We summarize this in the following lemma and give its proof for completeness.

We ask for a version with non-uniform weights which may shed light on the unrelated machines scheduling, where job $j$ has processing time $d_{ij}$ on machine $i$: