{"ID":2838064,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18546","arxiv_id":"2511.18546","title":"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}^n_{\u003e0}$, 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| \u003c \\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.","short_abstract":"Given positive integers $m, n$, a fractional assignment $x \\in [0,1]^{m \\times n}$ and weights $d \\in \\mathbb{R}^n_{\u003e0}$, 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| \u003c \\max_{j \\in [n]} d_j. \\] This...","url_abs":"https://arxiv.org/abs/2511.18546","url_pdf":"https://arxiv.org/pdf/2511.18546v1","authors":"[\"Siyue Liu\",\"Victor Reis\"]","published":"2025-11-23T17:28:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}