9 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…
Column Number of Delta-modular matrices: Refined Analysis via Sauer Matrices
Elizaveta Pribytkova, Dmitry Gribanov, Stanislav Moiseev
In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a -modular matrix $A \i…
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…
Near-optimal edge partitioning via intersecting families
Alexander Yakunin, Andrey Kupavskii, Alexander Sushin +1
We study the problem of edge partitioning, where the goal is to partition the edge set of a graph into parts. The replication factor of a vertex is the number of parts that…
LD-Leiden: Local Parallel Community Detection in Large Dynamic Networks
Grigoriy Bokov, Aleksandr Konovalov, Anna Uporova +3
Dynamic community detection must update high-quality modularity partitions after edge batches, yet full Leiden reruns make small changes scale with the whole snapshot. Existing dyn…
An improvement of degree-based hashing (DBH) graph partition method, using a novel metric
Anna Mastikhina, Oleg Senkevich, Dmitry Sirotkin +2
This paper examines the graph partition problem and introduces a new metric, MSIDS (maximal sum of inner degrees squared). We establish its connection to the replication factor (RF…
Graph partition method based on finite projective planes
Oleg Kruglov, Anna Mastikhina, Oleg Senkevich +2
We present a novel graph partition algorithm with a theoretical bound for the replication factor of \sqrt(n), which improves known constrained approaches (grid: 2* \sqrt(n)-1, toru…