Volume 18, No 1, 2011, P. 20-26

UDC 519.87+519.854
V. T. Dementiev, Yu. V. Shamardin
On a polinomial solving case of decentralized transportation problem

Abstract:
A case of decentralized transportation problem is considered, where a cost matrix has $n$ lines, $2n$ columns and a diagonal structure. An algorithm based on dynamic programming is proposed, that solves the problem with complexity $O(n^2)$.
Bibliogr. 1.

Keywords: decentralized transportation problem, dynamic programming.

Dementiev Vladimir Tikhonovich ^1,2
Shamardin Yurii Vladislavovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: demvt@math.nsc.ru, orlab@math.nsc.ru