Volume 15, No 3, 2008, P. 2230
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 NPhard. 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, NPcompleteness, approximate algorithm.
Dementiev Vladimir Tikhonovich ^{1}
Pyatkin Artem Valerevich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: artem@math.nsc.ru
