16 citations · 74 across the 16 of their papers we have counts for
17 papers
Column Number of Delta-modular matrices: Refined Analysis via Sauer Matrices
Elizaveta Pribytkova, Dmitry Gribanov, Stanislav Moiseev
In this paper, we build upon the analysis initiated by Gennadiy Averkov and Matthias Schymura (2022) and establish that the number of distinct columns of a -modular matrix $A \i…
Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy
Dmitry Gribanov, Dmitry Malyshev, Panos Pardalos
For a matrix of rank , the diagonal Frobenius number is defined as the minimum , such that, for any $b \in \text{sp…
Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
Grigorii Dakhno, Dmitry Gribanov, Nikita Kasianov +4
In our work, we consider the problem of computing a vector of minimum -norm such that , for any vector from a given subset of…
Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
M. Cherniavskii, D. Gribanov, D. Malyshev +1
For integers and a cost vector , we study two fundamental integer linear programming (ILP) problems: \[ \text{(Standard Form)} \quad \max\bigl\{c^\top x \co…
A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
D. Gribanov, D. Malyshev, P. Pardalos +1
In this paper, we consider the counting function for a parametric polyhedron , where $y \in R^{n_…
Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
Dmitry Gribanov, Dmitry Malyshev, Nikolai Zolotykh
In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solut…
A faster algorithm for counting the integer points number in -modular polyhedra (corrected version)
D. V. Gribanov, D. S. Malyshev
Let a polytope be defined by a system . We consider the problem of counting the number of integer points inside , assuming that is -modular, where the pol…
An FPTAS for the -modular multidimensional knapsack problem
D. V. Gribanov
It is known that there is no EPTAS for the -dimensional knapsack problem unless . It is true already for the case, when . But, an FPTAS still can exist for so…
A polynomial algorithm for minimizing discrete convic functions in fixed dimension
S. I. Veselov, D. V. Gribanov, N. Yu. Zolotykh +1
Recently classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the clas…
On lattice point counting in -modular polyhedra
D. V. Gribanov, N. Yu. Zolotykh
Let a polyhedron be defined by one of the following ways: (i) , where , and ; (ii…
On -Modular Integer Linear Problems In The Canonical Form And Equivalent Problems
D. V. Gribanov, I. A. Shumilov, D. S. Malyshev +1
Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type , where…
All 2-neighborly d-polytopes with at most d + 9 facets
Aleksandr N. Maksimenko, Dmitry V. Gribanov, Dmitry S. Malyshev
We give a complete enumeration of all 2-neighborly -polytopes with and less facets. All of them are realized as 0/1-polytopes, except a 6-polytope with 10 ve…
On the complexity of quasiconvex integer minimization problem
A. Yu. Chirkov, D. V. Gribanov, D. S. Malyshev +3
In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered in the p…
FPT-algorithms for some problems related to integer programming
D. V. Gribanov, D. S. Malyshev, P. M. Pardalos +1
In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices include…
The Width and Integer Optimization on Simplices With Bounded Minors of the Constraint Matrices
D. V. Gribanov, A. Y. Chirkov
In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are…
FPT-algorithms for The Shortest Lattice Vector and Integer Linear Programming Problems
D. V. Gribanov
In this paper, we present FPT-algorithms for special cases of the shortest vector problem (SVP) and the integer linear programming problem (ILP), when matrices included to the prob…
On integer programing with bounded determinants
Dmitry Gribanov, Sergey Veselov
Let be an integral matrix, and let be an -dimensional polytope. The width of is defined as $ w(P)=min\{ x\in \mathbb{Z}^n\setminus…