File(s) under permanent embargo
Between a rock and a hard place: the two-to-one assignment problem
conference contribution
posted on 2012-01-01, 00:00 authored by D Goossens, Sergey PolyakovskiySergey Polyakovskiy, F C R Spieksma, G J WoegingerWe 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.
History
Event
Approximation and online algorithms. International workshop (7th : 2009 : Copenhagen, Denmark)Volume
5893Series
Lecture Notes in Computer SciencePagination
159 - 169Publisher
SpringerLocation
Copenhagen, DenmarkPlace of publication
Berlin, GermanyPublisher DOI
Start date
2009-09-10End date
2009-09-11ISSN
0302-9743eISSN
1611-3349ISBN-10
3642124496Language
engPublication classification
E1.1 Full written paper - refereedCopyright notice
2012, Springer-VerlagEditor/Contributor(s)
UnknownTitle of proceedings
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Usage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC