5 papers · 1 filter
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…
On the Column Number of Delta-Modular Matrices: an Bound via the Shifted Heller Constant
Elizaveta Pribytkova, Dmitry Gribanov, Dmitrii Gribanov +2
In this paper, we build on the analysis initiated by Averkov and Schymura (2022) and prove that the shifted Heller constant for matrices with rows is at most for all…
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…