Weighted Chairman Assignment and Flow-Time Scheduling

Abstract

Given positive integers $m,n$, a fractional assignment $x\in [0,1{]}^{m\times n}$ and weights $d\in {\mathbb{R}}_{>0}^n$, we show that there exists an assignment $y\in \{0,1{\}}^{m\times n}$ so that for every $i\in [m]$ and $t\in [n]$, \[ \Big|\sum_{j \in [t]} d_j (x_{ij} - y_{ij}) \Big| < \max_{j \in [n]} d_j. \] This generalizes a result of Tijdeman (1973) on the unweighted version, known as the chairman assignment problem. This also confirms a special case of the single-source unsplittable flow conjecture with arc-wise lower and upper bounds due to Morell and Skutella (IPCO 2020). As an application, we consider a scheduling problem where jobs have release times and machines have closing times, and a job can only be scheduled on a machine if it is released before the machine closes. We give a $3$-approximation algorithm for maximum flow-time minimization.