Title: Between a rock and a hard place: the two-to-one assignment problem
Authors: Goossens, Dries ×
Polyakovski, S.
Spieksma, Frits
Woeginger, G. #
Issue Date: 2012
Publisher: Springer-Verlag
Series Title: Mathematical Methods of Operations Research vol:76 issue:2 pages:223-237
Abstract: We describe the two-to-one assignment problem, a problem in between the axial three-index assignment problem and the three-dimensional matching problem, having applications in various domains. For the (relevant) case of decomposable costs satisfying the triangle inequality we provide, on the positive side, two constant factor approximation algorithms. These algorithms involve solving minimum weight matching problems and transportation problems, leading to a 2-approximation, and a $${\frac{3}{2}}$$ -approximation. Moreover, we further show that the best of these two solutions is a -approximation for our problem. On the negative side, we show that the existence of a polynomial time approximation scheme for our problem would imply P = NP. Finally, we report on some computational experiments showing the performance of the described heuristics.
ISSN: 1432-2994
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
BetweenaRock.pdf Published 275KbAdobe 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