The approximability of three-dimensional assignment problems with bottleneck objective |
| |
| Authors: | Dries Goossens Sergey Polyakovskiy Frits C. R. Spieksma Gerhard J. Woeginger |
| |
| Affiliation: | 1. Operations Research Group, Katholieke Universiteit Leuven, Naamsestraat 69, 3000, Leuven, Belgium
2. Department of Mathematics, TU Eindhoven, P.O. Box 513, 5600?MB, Eindhoven, The Netherlands
|
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
