Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/94120
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGoossens, D.en
dc.contributor.authorPolyakovskiy, S.en
dc.contributor.authorSpieksma, F.en
dc.contributor.authorWoeginger, G.en
dc.date.issued2012en
dc.identifier.citationMathematical Methods of Operations Research, 2012; 76(2):223-237en
dc.identifier.issn1432-5217en
dc.identifier.issn1432-5217en
dc.identifier.urihttp://hdl.handle.net/2440/94120-
dc.description.abstractWe 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-approximation. Moreover, we further show that the best of these two solutions is a 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.en
dc.description.statementofresponsibilityDries Goossens, Sergey Polyakovskiy, Frits C.R. Spieksma and Gerhard J. Woegingeren
dc.language.isoEnglishen
dc.publisherSpringer Verlagen
dc.rights© Springer-Verlag 2012en
dc.subjectAssignment problem; matching problem; efficient algorithm; approximationen
dc.titleBetween a rock and a hard place: the two-to-one assignment problemen
dc.typeJournal articleen
dc.identifier.rmid0030007731en
dc.identifier.doi10.1007/s00186-012-0397-2en
dc.identifier.pubid71900-
pubs.library.collectionComputer Science publicationsen
pubs.library.teamDS09en
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidPolyakovskiy, S. [0000-0001-9489-1972]en
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.