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 \({\frac{4}{3}}\) -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.
Similar content being viewed by others
References
Bandelt H-J, Crama Y, Spieksma FCR (1994) Approximation algorithms for multidimensional assignment problems with decomposable costs. Discret Appl Math 49: 25–50
Biyani P, Wu X, Sinha A (2005) Joint classification and pairing of human chromosomes. IEEE/ACM Trans Comput Biol Bioinf 2: 102–109
Burkard RE, Rudolf R, Woeginger GJ (1996) Three-dimensional axial assignment problems with decomposable cost coefficients. Discret Appl Math 65: 123–140
Crama Y, Spieksma FCR (1992) Approximation algorithms for three-dimensional assignment problems with triangle inequalities. Eur J Oper Res 60: 273–279
Dutta A, Tsiotras P (2008) Egalitarian peer-to-peer satellite refueling strategy. J Spacecr Rocket 45: 608–618
Friesen D, Langston M (1991) Analysis of a compound bin packing algorithm. SIAM J Discret Math 4: 61–79
Goossens D, Polyakovskiy S, Spieksma FCR, Woeginger GJ (2010) The approximability of three-dimensional assignment problems with bottleneck objective. Optim Lett 4: 7–16
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Kann V (1991) Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf Process Lett 37: 27–35
Magyar G, Johnsson M, Nevalainen O (2000) An adaptive hybrid genetic algorithm for the three-matching problem. IEEE Trans Evol Comput 4: 135–146
Petrank E (1994) The hardness of approximation: gap location. Comput Complex 4: 133–157
Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin
Spieksma FCR, Woeginger GJ (1996) Geometric three-dimensional assignment problems. Eur J Oper Res 91: 611–618
Urban T, Russel R (2003) Scheduling sport competitions on multiple venues. Eur J Oper Res 148: 302–311
Wilson B (1963) Surf city. Liberty records
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.033.403, by BSIK grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society), and by OT Grant OT/07/015. An earlier version of this work appeared in the Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009).
Rights and permissions
About this article
Cite this article
Goossens, D., Polyakovskiy, S., Spieksma, F.C.R. et al. Between a rock and a hard place: the two-to-one assignment problem. Math Meth Oper Res 76, 223–237 (2012). https://doi.org/10.1007/s00186-012-0397-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-012-0397-2