**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