Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…