EDBT 2026 Demo / reviewers in the wild / expert
Dmitry V. Gribanov
dblp:163/1850 · also Dmitriy V. Gribanov
· DBLP profile ↗
6ranked-venue papers
4as first author
3since 2021 · last 2026
0000-0002-4005-9483ORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 6 · 4 first-author · 3 since 2021
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy SettingabstractWe study the standard-form ILP problem c^⊤ x → max Ax = b, x ∈ ℤ_{≥ 0}ⁿ, where A ∈ ℤ^{k× n} has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k× k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κ_k denote the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. Up to polynomial factors in the input size, the optimization problem can be solved in time O(κ_k)^{2k} Δ², and the corresponding feasibility problem in time O(κ_k)^kΔ. Using the best currently known bound κ_k = Õ(log^{1/4}k), this yields running times O(log k)^{k/2(1+o(1))} Δ² and O(log k)^{k/4(1+o(1))} Δ, respectively. Under the Komlós conjecture, the dependence on k in both running times reduces to 2^O(k). Dmitry V. Gribanov, Tagir Khayaleyev, Mikhail Cherniavskii, Maxim Klimenko, Dmitriy S. Malyshev, Stanislav Moiseev |
ESA | 1 |
| 2024 | On Δ-modular integer linear problems in the canonical form and equivalent problems
Dmitry V. Gribanov, Ivan A. Shumilov, Dmitriy S. Malyshev, Panos M. Pardalos |
J. Glob. Optim. | 1 |
| 2024 | Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
Dmitry V. Gribanov, Ivan A. Shumilov, Dmitriy S. Malyshev, Nikolai Yu. Zolotykh |
J. Glob. Optim. | 1 |
| 2020 | A polynomial algorithm for minimizing discrete convic functions in fixed dimension
Sergey I. Veselov, Dmitry V. Gribanov, Nikolai Yu. Zolotykh, Aleksandr Yu. Chirkov |
Discret. Appl. Math. | 2 |
| 2019 | On the complexity of quasiconvex integer minimization problem
Aleksandr Yu. Chirkov, Dmitry V. Gribanov, Dmitriy S. Malyshev, Panos M. Pardalos, Sergey I. Veselov, Nikolai Yu. Zolotykh |
J. Glob. Optim. | 2 |
| 2017 | The computational complexity of three graph problems for instances with bounded minors of constraint matrices
Dmitry V. Gribanov, Dmitriy S. Malyshev |
Discret. Appl. Math. | 1 |