|
Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2010, Volume 16, Number 3, Pages 140–145
(Mi timm584)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Investigation of one algorithm for solving problems of integer linear programming
A. A. Kolokolov, T. G. Orlovskaya Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Science
Abstract:
A famous algorithm for solving problems of integer linear programming based on the method of regular partitions is investigated. In particular, it is shown that the algorithm is regular with respect to some of such partitions in the case of problems that simplify its application. A subclass of matrices generating such problems is given. A family of problems of special form is constructed for which the algorithm is exponential with respect to the length of the input.
Keywords:
integer programming, unimodular transformations, regular partitions.
Received: 28.04.2010
Citation:
A. A. Kolokolov, T. G. Orlovskaya, “Investigation of one algorithm for solving problems of integer linear programming”, Trudy Inst. Mat. i Mekh. UrO RAN, 16, no. 3, 2010, 140–145
Linking options:
https://www.mathnet.ru/eng/timm584 https://www.mathnet.ru/eng/timm/v16/i3/p140
|
Statistics & downloads: |
Abstract page: | 318 | Full-text PDF : | 96 | References: | 42 | First page: | 3 |
|