Dmitry V. Gribanov

dblp:163/1850 · also Dmitriy V. Gribanov · DBLP profile ↗
← Back
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
YearPublicationVenuePosition
2026 Algorithms for Standard-Form ILP Problems via Komlós' Discrepancy Setting
abstract
We 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
ESA1
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