4 papers
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…
Enumerating Complexity Revisited
Alexander Shekhovtsov, Georgii Zakharov, Nikolay Vereshchagin
We study the relation between deterministic and randomized Kolmogorov complexity of sets . Let be the length of a shortest inpu…