Volume 15, No 3, 2008, P. 22-30

UDC 519.87+519.854
V. T. Dementiev, A. V. Pyatkin
On decentralized transportation problem

Abstract:
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 approximate polynomial algorithm with a guaranteed ratio is proposed in the case of the same demand values. 
Bibl. 3.

Keywords: transportation problem, bilevel programming, algorithmic complexity, NP-completeness, approximate algorithm.

Dementiev Vladimir Tikhonovich ¹
Pyatkin Artem Valerevich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: artem@math.nsc.ru