2026-08-12T01:35:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25385 2026-03-19T13:04:20Z ddc:004 open_access

Weighted Chairman Assignment and Flow-Time Scheduling Liu, Siyue Reis, Victor prefix discrepancy flow-time scheduling unsplittable flow Given positive integers m, n, a fractional assignment x ∈ [0,1]^{m × n} and weights d ∈ ℝⁿ_{> 0}, we show that there exists an assignment y ∈ {0,1}^{m × n} so that for every i ∈ [m] and t ∈ [n], |∑_{j ∈ [t]} d_j (x_{ij} - y_{ij})| < max_{j ∈ [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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siyue Liu and Victor Reis 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.98 urn:nbn:de:0030-drops-253858 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.98 eng https://creativecommons.org/licenses/by/4.0/legalcode