A new effective dynamic program for an investment optimization problem

Gafarov E.R.; Dolgui A.; Lazarev Alexander Alexeevich; Werner F.

doi:10.1134/S0005117916090101

Publications

Article

A new effective dynamic program for an investment optimization problem

Automation and Remote Control. 2016. Vol. 77. No. 9. P. 1633-1648.

Gafarov E., Dolgui A., Lazarev A. A., Werner F.

After a series of publications of T.E. O’Neil et al. (e.g. in 2010), dynamic programming seems to be the most promising way to solve knapsack problems. Some techniques are known to make dynamic programming algorithms (DPA) faster. One of them is the graphical method that deals with piecewise linear Bellman functions. For some problems, it was previously shown that the graphical algorithm has a smaller running time in comparison with the classical DPA and also some other advantages. In this paper, an exact graphical algorithm (GrA) and a fully polynomial-time approximation scheme based on it are presented for an investment optimization problem having the best known running time. The algorithms are based on new Bellman functional equations and a new way of implementing the GrA.

Language: English

DOI

Keywords: algorithm

Publication based on the results of: Development and research of new mathematical models in socio-economic and political spheres(2016)

Mathematical Methods in Engineering

Springer, 2007.

Added: Jan 22, 2015

24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings

Heidelberg: Springer, 2013.

Added: Apr 11, 2019

Особенности преподавания методов дискриминантного анализа для подготовки специалистов по направлению «бизнес-информатика»

Сизых Н. В., Сизых Д. С. В кн.: Монография "Образование: опыт и перспективы развития". ИД «Среда», 2019. С. 107-133.

Peculiarities of lecturing discriminant analysis methods for training specialists in the field of "business informatics", that is, specialists for whom understanding the model, the algorithm for its practical implementation and approaches to assessing and analyzing the results obtained, are considered. And also - an understanding of purpose, where, when and how it is possible and necessary to use this method. All this determines the practical orientation of the lectouring process.

Added: Aug 9, 2019

Topological classification of Ω-stable flows on surfaces by means of effectively distinguishable multigraphs

Vladislav E. Kruglov, Dmitry S. Malyshev, Olga V. Pochinka. arxiv.org. math. Cornell University, 2017. No. 1706.01695v1.

Structurally stable (rough) flows on surfaces have only finitely many singularities and finitely many closed orbits, all of which are hyperbolic, and they have no trajectories joining saddle points. The violation of the last property leads to Ω-stable flows on surfaces, which are not structurally stable. However, in the present paper we prove that a topological classification of such flows is also reduced to a combinatorial problem. Our complete topological invariant is a multigraph, and we present a polynomial-time algorithm for the distinction of such graphs up to an isomorphism. We also present a graph criterion for orientability of the ambient manifold and a graph-associated formula for its Euler characteristic. Additionally, we give polynomial-time algorithms for checking the orientability and calculating the characteristic.

Added: Sep 11, 2017

Языки спецификаций моделей Крипке на основе темпоральных логик и их выразительные возможности

Гнатенко А. Р., Захаров В. А. В кн.: . С. 131-133.

The expressive power of a new variant of temporal logic LP-CTL * is studied. In this logic, two classes of LP-1-LTL and LP-n-LTL formulas were distinguished and it was shown that the LP-1-LTL fragment more expressive than the known temporal logic of linear time LTL, and the LP-n-LTL fragment has the same expressive possibilities as the second-order monadic logic S1S.

Added: Jun 14, 2018

Computing Intersection Numbers and Bases of Cohomology Groups for Triangulated Closed Three-Dimensional Manifolds

Yakovlev E., Epifanov V. Lobachevskii Journal of Mathematics. 2019. Vol. 40. No. 5. P. 690-698.

We solve some computational problems for triangulated closed three-dimensional manifolds using groups of simplicial homology and cohomology modulo 2. Two efficient algorithms for computing intersection numbers of 1- and 2-dimensional cycles are developed. Using these algorithms it is possible to construct a basis of the cohomology group from a given basis of the homology group of complementary dimension.

Added: Oct 8, 2019

О древовидных режимах работы хэш-функций

Дали Ф. А., Миронкин В. О. Проблемы информационной безопасности. Компьютерные системы. 2018. № 1. С. 113-121.

Two models of the tree modes of hash functions are introduced. For each model algorithms of computing of the hash code are formulated and their numerical characteristics are obtained. In terms of the constructed models we classify some existing algorithms for parallel hashing and identify some weaknesses of corresponding primitives.

Added: May 28, 2018

Об универсальном древовидном режиме выработки хэш-кода

Богданов Д. С., Дали Ф. А., Миронкин В. О. Современные информационные технологии и ИТ-образование. 2018. Т. 14. № 2. С. 419-425.

Classical approaches to the construction of hash function modes, based on the using of iterative procedures, do not allow efficient processing of large amounts of data and can’t be adapted to parallel computing architectures. It applies to both the Russian cryptographic standard GOST R 34.11-2012, which determines the algorithm and procedure for calculating the hash function, as well as many other foreign standards (for example, SHA-3). The absence of standards for parallelized modes for the hash functions of GOST R 34.11-2012 creates an urgent need for the development of the domestic standard of the parallelized mode of hash code.

This article is devoted to the research and development of new modes of hash code generation that allow efficient parallelization of the computation process and provide cryptographic resistance satisfying modern requirements. This work continues the research carried out by the authors, and offers a fundamentally new tree mode of hash code generation ("FT-mode"), based on l-ary hash trees and allowed to use any compression mapping for a mechanism of forming tree nodes. The resistance of the mode is completely determined by the resistance of the corresponding compressive mapping. In particular, the FT-mode allows using block ciphers and substitution transformations to form nodes of a hash tree along with compression functions and hash functions. In addition, the FT-mode excludes the main functional disadvantages of the known tree modes of hash code generation that affect their operational, technical and cryptographic quality.Within the framework of the present research a number of characteristics of FT-mode are calculated, and a comparative analysis of the time and computational complexity of implementations of FT-mode and some foreign tree hash modes is carried out. The corresponding results showed that the developed mode is not inferior to any of the considered modes.

Added: Nov 8, 2018

Search on the enumeration tree in the multiprocessor job-shop problem

Lazarev A. A., Carballo L., Vakhania N. et al. In bk.: IFAC Proceedings Volumes 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucharest, 23-25 May 2012. Bucharest: IFAC Technical Committee, 2012. P. 381-386.

We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented.

Added: Feb 12, 2013