Between a rock and a hard place: the two‐to‐one assignment problem

Between a rock and a hard place: the two‐to‐one assignment problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: combinatorial optimization, heuristics
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 3 2 equ1 ‐approximation. Moreover, we further show that the best of these two solutions is a 4 3 equ2 ‐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.

Reviews

Required fields are marked *. Your email address will not be published.