Geodesic
A strongly-polynomial algorithm for solving the general problem of least modules
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 13 (2010) no. 2, pp. 161-181.

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

The algorithm of polynomial algebraic complexity (a strongly-polynomial algorithm) to solve a classical problem of mathematical programming concerning minimization of the weighted sum of modules of part of variables with linear constraints (equalities imposed on all variables) has been substantiated. The algorithm is given in its explicit form. The estimation of the algorithm complexity is presented. The simulation has been carried out. 
@article{SJVM_2010_13_2_a2,
     author = {V. V. Mironov},
     title = {A strongly-polynomial algorithm for solving the general problem of least modules},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {161--181},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2010_13_2_a2/}
}
TY  - JOUR
AU  - V. V. Mironov
TI  - A strongly-polynomial algorithm for solving the general problem of least modules
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2010
SP  - 161
EP  - 181
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2010_13_2_a2/
LA  - ru
ID  - SJVM_2010_13_2_a2
ER  - 
%0 Journal Article
%A V. V. Mironov
%T A strongly-polynomial algorithm for solving the general problem of least modules
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2010
%P 161-181
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2010_13_2_a2/
%G ru
%F SJVM_2010_13_2_a2
V. V. Mironov. A strongly-polynomial algorithm for solving the general problem of least modules. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 13 (2010) no. 2, pp. 161-181. http://geodesic.mathdoc.fr/item/SJVM_2010_13_2_a2/

[1] Smale S., “Mathematical problems for the next century”, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, 271–294 | MR | Zbl

[2] Golikov A. I., Evtushenko Yu. G., “Otyskanie normalnykh reshenii v zadachakh lineinogo programmirovaniya”, Zhurn. vychisl. matem. i matem. fiz., 40:12 (2000), 1766–1786 | MR | Zbl

[3] Yudin D. B., Nemirovskii A. S., “Informatsionnaya slozhnost i effektivnye metody resheniya vypuklykh ekstremalnykh zadach”, Ekonomika i matem. metody, 12:2 (1976), 357–369 | MR | Zbl

[4] Rozenfeld B. A., Mnogomernye prostranstva, Nauka, M., 1966 | MR

[5] Mudrov V. I., Kushko V. L., Metod naimenshikh modulei, Znanie, M., 1971

[6] Bakhshiyan B. Ts., Nazirov R. R., Elyasberg P. E., Opredelenie i korrektsiya dvizheniya, Nauka, M., 1980 | MR | Zbl

[7] Nazirov R. R., Vliyanie oshibok modeli dvizheniya na tochnost opredeleniya polozheniya ISZ vdol ego orbity, Izd-vo IKI AN SSSR, M., 1983

[8] Todc M. J., “Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems”, Math. Programming, 35:2 (1986), 173–192 | DOI | MR

[9] Coppersmith D., Winograd S., Matrix multiplication via arithmetic progression, Preprint, Dept. of Math. Sci. IBM Thomas J. Watson Res. Centr., 1986, Nov. | MR

[10] Ikramov Kh. D., Chislennoe reshenie matrichnykh uravnenii, Nauka, M., 1984 | MR | Zbl

[11] Crandall R., Klivington J., Fast matrix algebra on Apple G9, Advanced Computation Group, Apple Computer, 2000

[12] Kantorovich L. V., Akilov G. P., Funktsionalnyi analiz v normirovannykh prostranstvakh, Nauka, M., 1977 | MR