An optimal algorithm for the Bottleneck
transportation problem with a fixed number of sources
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.
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.