Geodesic
On decentralized transportation problem
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 3, pp. 22-30.

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

A decentralized transportation problem is considered, where the customers act individually maximizing their own profit, while the producer can only determine the sequence of their service. It is shown that this problem is NP-hard. An aproximate polynomial algorithm with a guaranteed ratio is proposed in the case of the same demand values. Bibl. 3.
Mots-clés : transportation problem
Keywords: bilevel programming, algorithmic complexity, NP-completeness, approximate algorithm. 
@article{DA_2008_15_3_a2,
     author = {V. T. Dement'ev and A. V. Pyatkin},
     title = {On decentralized transportation problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {22--30},
     publisher = {mathdoc},
     volume = {15},
     number = {3},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_3_a2/}
}
TY  - JOUR
AU  - V. T. Dement'ev
AU  - A. V. Pyatkin
TI  - On decentralized transportation problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 22
EP  - 30
VL  - 15
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_3_a2/
LA  - ru
ID  - DA_2008_15_3_a2
ER  - 
%0 Journal Article
%A V. T. Dement'ev
%A A. V. Pyatkin
%T On decentralized transportation problem
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 22-30
%V 15
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_3_a2/
%G ru
%F DA_2008_15_3_a2
V. T. Dement'ev; A. V. Pyatkin. On decentralized transportation problem. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 3, pp. 22-30. http://geodesic.mathdoc.fr/item/DA_2008_15_3_a2/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Dinits E. A., “Algoritm porazryadnogo sokrascheniya nevyazok i transportnye zadachi”, Issledovaniya po diskretnoi matematike, Nauka, M., 1973, 46–57

[3] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, M., 1978, 432 pp. | MR