M. Cherniavskii

collaborators

3 papers

cs.DM2026

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 $k$ groups of $n_{1}, \dots, n_{k}$ agents. We look at the worst downward deviation $\textit{PROP}(n_1,\ldots…

cs.DS2026

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined $2^{O (k)}$ -analysis)

Dmitry Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii +3

We study the standard-form ILP problem $max {c^{⊤} x : A x = b, x \in Z_{\geq 0}^{n}}$ , where $A \in Z^{k \times n}$ has full row rank. We obtain refined FPT algorithms par…

cs.CC2024

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)

M. Cherniavskii, D. Gribanov, D. Malyshev +1

For integers $k, n \geq 0$ and a cost vector $c \in Z^{n}$ , we study two fundamental integer linear programming (ILP) problems: \[ \text{(Standard Form)} \quad \max\bigl\{c^\top x \co…

Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined 2O(k)-analysis)

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting (Refined $2^{O (k)}$ -analysis)