| Article ID: | iaor200973046 |
| Country: | Germany |
| Volume: | 4 |
| Issue: | 1 |
| Start Page Number: | 7 |
| End Page Number: | 16 |
| Publication Date: | Dec 2009 |
| Journal: | Optimization Letters |
| Authors: | Spieksma Frits C R, Goossens Dries, Polyakovskiy Sergey, Woeginger Gerhard J |
We discuss two special cases of the three-dimensional bottleneck assignment problem where a certain underlying cost function satisfies the triangle inequality. We present polynomial time 2-approximation algorithms for the broadest class of these special cases, and we prove that (unless P = NP) this factor 2 is best possible even in the highly restricted setting of the Euclidean plane.