Geodesic
Investigation of one algorithm for solving problems of integer linear programming
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 140-145

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TIMM_2010_16_3_a13,
     author = {A. A. Kolokolov and T. G. Orlovskaya},
     title = {Investigation of one algorithm for solving problems of integer linear programming},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {140--145},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/}
}
TY  - JOUR
AU  - A. A. Kolokolov
AU  - T. G. Orlovskaya
TI  - Investigation of one algorithm for solving problems of integer linear programming
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 140
EP  - 145
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/
LA  - ru
ID  - TIMM_2010_16_3_a13
ER  - 
%0 Journal Article
%A A. A. Kolokolov
%A T. G. Orlovskaya
%T Investigation of one algorithm for solving problems of integer linear programming
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 140-145
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/
%G ru
%F TIMM_2010_16_3_a13
A. A. Kolokolov; T. G. Orlovskaya. Investigation of one algorithm for solving problems of integer linear programming. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 140-145. http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/