6 papers
SP-Allreduce: Symmetric Tree Schedules for Tori and Beyond
Mikhail Cherniavskii, Andrey Kupavskii, Georgy Mironov +1
Allreduce is a fundamental communication primitive in large-scale distributed training, and torus interconnects remain widely deployed in high-performance systems. We introduce SP-…
Approximation algorithms via discrepancy with hard constraints
Mikhail Cherniavskii, Andrey Kupavskii, Stanislav Moiseev +1
In this paper, we present a discrepancy-based approach to cost-preserving rounding under hard constraints. Starting from a feasible fractional solution, our rounding procedure pres…
Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings
Mikhail Cherniavskii, Arseni Fedorovich, Mikhail Koshelev +4
We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a -approximation without release dat…
Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy
Alexander Shekhovtsov, Georgy Sokolov, Mikhail Cherniavskii +1
This paper studies the problem of fair division of indivisible goods among groups of agents. We look at the worst downward deviation $\textit{PROP}(n_1,\ldots…
Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined -analysis)
Dmitry Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii +3
We study the standard-form ILP problem , where has full row rank. We obtain refined FPT algorithms par…
Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
M. Cherniavskii, D. Gribanov, D. Malyshev +1
For integers and a cost vector , we study two fundamental integer linear programming (ILP) problems: \[ \text{(Standard Form)} \quad \max\bigl\{c^\top x \co…