Article ID: | iaor20125893 |
Volume: | 76 |
Issue: | 2 |
Start Page Number: | 223 |
End Page Number: | 237 |
Publication Date: | Oct 2012 |
Journal: | Mathematical Methods of Operations Research |
Authors: | Woeginger Gerhard, Goossens Dries, Polyakovskiy Sergey, Spieksma Frits |
Keywords: | combinatorial optimization, heuristics |
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