Title: The approximability of three-dimensional assignment problems with bottleneck objective
Authors: Goossens, Dries ×
Polyakovskiy, S.
Spieksma, Frederik
Woeginger, G.J. #
Issue Date: Jan-2010
Publisher: Springer Heidelberg
Series Title: Optimization Letters vol:4 issue:1 pages:7-16
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.
ISSN: 1862-4472
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
TheApproximability.pdf Published 332KbAdobe PDFView/Open Request a copy

These files are only available to some KU Leuven Association staff members


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science