DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.98

Weighted Chairman Assignment and Flow-Time Scheduling

Authors: Siyue Liu and Victor Reis

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

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.

Cite as

Siyue Liu and Victor Reis. Weighted Chairman Assignment and Flow-Time Scheduling. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 98:1-98:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2026.98,
  author =	{Liu, Siyue and Reis, Victor},
  title =	{{Weighted Chairman Assignment and Flow-Time Scheduling}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{98:1--98:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.98},
  URN =		{urn:nbn:de:0030-drops-253858},
  doi =		{10.4230/LIPIcs.ITCS.2026.98},
  annote =	{Keywords: prefix discrepancy, flow-time scheduling, unsplittable flow}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.18

A Randomized Rounding Approach for DAG Edge Deletion

Authors: Sina Kalantarzadeh, Nathan Klein, and Victor Reis

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

In the DAG Edge Deletion problem, we are given an edge-weighted directed acyclic graph and a parameter k, and the goal is to delete the minimum weight set of edges so that the resulting graph has no paths of length k. This problem, which has applications to scheduling, was introduced in 2015 by Kenkre, Pandit, Purohit, and Saket. They gave a k-approximation and showed that it is UGC-Hard to approximate better than ⌊0.5k⌋ for any constant k ≥ 4 using a work of Svensson from 2012. The approximation ratio was improved to 2/3(k+1) by Klein and Wexler in 2016. In this work, we introduce a randomized rounding framework based on distributions over vertex labels in [0,1]. The most natural distribution is to sample labels independently from the uniform distribution over [0,1]. We show this leads to a (2-√2)(k+1) ≈ 0.585(k+1)-approximation. By using a modified (but still independent) label distribution, we obtain a 0.549(k+1)-approximation for the problem, as well as show that no independent distribution over labels can improve our analysis to below 0.542(k+1). Finally, we show a 0.5(k+1)-approximation for bipartite graphs and for instances with structured LP solutions. Whether this ratio can be obtained in general is open.

Cite as

Sina Kalantarzadeh, Nathan Klein, and Victor Reis. A Randomized Rounding Approach for DAG Edge Deletion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kalantarzadeh_et_al:LIPIcs.APPROX/RANDOM.2025.18,
  author =	{Kalantarzadeh, Sina and Klein, Nathan and Reis, Victor},
  title =	{{A Randomized Rounding Approach for DAG Edge Deletion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.18},
  URN =		{urn:nbn:de:0030-drops-243840},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.18},
  annote =	{Keywords: Approximation Algorithms, Randomized Algorithms, Linear Programming, Graph Algorithms, Scheduling}
}

Search Results

Documents authored by Reis, Victor

Weighted Chairman Assignment and Flow-Time Scheduling

Abstract

Cite as

A Randomized Rounding Approach for DAG Edge Deletion

Abstract

Cite as

Thanks for your feedback!

Could not send message