Zobrazeno 1 - 10
of 391
pro vyhledávání: '"Gribanov, A. V."'
In this work we consider the problem of computing the $(\min, +)$-convolution of two sequences $a$ and $b$ of lengths $n$ and $m$, respectively, where $n \geq m$. We assume that $a$ is arbitrary, but $b_i = f(i)$, where $f(x) \colon [0,m) \to \mathbb
Externí odkaz:
http://arxiv.org/abs/2209.04812
Let $A \in Z^{m \times n}$, $rank(A) = n$, $b \in Z^m$, and $P$ be an $n$-dimensional polyhedron, induced by the system $A x \leq b$. It is a known fact that if $F$ is a $k$-face of $P$, then there exist at least $n-k$ linearly independent inequaliti
Externí odkaz:
http://arxiv.org/abs/2203.03907
Autor:
Gribanov, D. V., Malyshev, D. S.
Publikováno v:
Siberian Electronic Mathematical Reports, 19(2), pp. 613-626 (2022)
Let a polytope $P$ be defined by a system $A x \leq b$. We consider the problem of counting the number of integer points inside $P$, assuming that $P$ is $\Delta$-modular, where the polytope $P$ is called $\Delta$-modular if all the rank sub-determin
Externí odkaz:
http://arxiv.org/abs/2110.01732
Autor:
Gribanov, D. V.
Publikováno v:
In MOTOR 2021, Irkutsk, Russia, July 5-10, 2021, Proceedings. Springer-Verlag, Berlin, Heidelberg, 79-95 (2021)
It is known that there is no EPTAS for the $m$-dimensional knapsack problem unless $W[1] = FPT$. It is true already for the case, when $m = 2$. But, an FPTAS still can exist for some other particular cases of the problem. In this note, we show that t
Externí odkaz:
http://arxiv.org/abs/2103.07257
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 classes of convex functions, strictly quasiconvex functions and the class
Externí odkaz:
http://arxiv.org/abs/2011.00598
Autor:
Gribanov, D. V., Zolotykh, N. Yu.
Publikováno v:
Optim Lett 16, 1991-2018 (2022)
Let a polyhedron $P$ be defined by one of the following ways: (i) $P = \{x \in R^n \colon A x \leq b\}$, where $A \in Z^{(n+k) \times n}$, $b \in Z^{(n+k)}$ and $rank\, A = n$; (ii) $P = \{x \in R_+^n \colon A x = b\}$, where $A \in Z^{k \times n}$,
Externí odkaz:
http://arxiv.org/abs/2010.05768
We study the proximity of the optimal value of the m-dimensional knapsack problem to the optimal value of that problem with the additional restriction that only one type of items is allowed to include in the solution. We derive exact and asymptotic f
Externí odkaz:
http://arxiv.org/abs/2004.08589
Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $\max\{c^\top x \colon A x = b,\, x \in \mathbb{Z}^n_{\geq 0}\}$, where all the entries of $A,b,c$ are integer, parameterized by the number of
Externí odkaz:
http://arxiv.org/abs/2002.01307
We give a complete enumeration of all 2-neighborly $d$-polytopes with $d+9$ and less facets. All of them are realized as 0/1-polytopes, except a 6-polytope $P_{6,10,15}$ with 10 vertices and 15 facets, and pyramids over $P_{6,10,15}$. In particular,
Externí odkaz:
http://arxiv.org/abs/1912.03900
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.