An optimal algorithm for the Bottleneck transportation problem with a fixed number of sources




Abstract

We investigate a special case of the Bottleneck transportation problem where the number s of sources is bounded by a constant and not part of the input. For the subcase s=2, a best possible linear time algorithm has been derived by Varadarajan [Operations Research Letters 10 (1991), 525--529]. In this note we show that for any fixed number s >= 1, the Bottleneck transportation problem with s sources can be solved in linear time. The algorithm is conceptually simple and easy to implement.

Download Information

Click on the following title to view and download the paper in PostScript format.

An optimal algorithm for the Bottleneck transportation problem with a fixed number of sources (6 pages, 369 KB)
,
Dorit S. Hochbaum and Gerhard J. Woeginger. Operations Research Letters. 24, 1999, 25-28.


dorit@hochbaum.ieor.berkeley.edu
7/30/98