4 papers · 1 filter
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…
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…
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…