Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/88308
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Goossens, D. | - |
dc.contributor.author | Polyakovskiy, S. | - |
dc.contributor.author | Spieksma, F. | - |
dc.contributor.author | Woeginger, G. | - |
dc.contributor.editor | Bampis, E. | - |
dc.contributor.editor | Jansen, K. | - |
dc.date.issued | 2010 | - |
dc.identifier.citation | Lecture Notes in Artificial Intelligence, 2010 / Bampis, E., Jansen, K. (ed./s), vol.5893 LNCS, pp.159-169 | - |
dc.identifier.isbn | 3642124496 | - |
dc.identifier.isbn | 9783642124495 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2440/88308 | - |
dc.description.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-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. | - |
dc.description.statementofresponsibility | Dries Goossens, Sergey Polyakovskiy, Frits C.R. Spieksma, and Gerhard J. Woeginger | - |
dc.language.iso | en | - |
dc.publisher | Springer-Verlag Berlin | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science; 5893 | - |
dc.rights | © Springer-Verlag Berlin Heidelberg 2010 | - |
dc.source.uri | http://dx.doi.org/10.1007/978-3-642-12450-1_15 | - |
dc.subject | Assignment problem matching problem; efficient algorithm; approximation; | - |
dc.title | Between a rock and a hard place: the two-to-one assignment problem | - |
dc.type | Conference paper | - |
dc.contributor.conference | 7th International Workshop on Approximation and Online Algorithms (10 Sep 2009 - 11 Sep 2009 : Copenhagen, Denmark) | - |
dc.identifier.doi | 10.1007/978-3-642-12450-1_15 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Polyakovskiy, S. [0000-0001-9489-1972] | - |
Appears in Collections: | Aurora harvest 2 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.