Between a rock and a hard place: the two-to-one assignment problem
Autor: | Goossens, D.R., Polyakovskiy, S., Spieksma, F.C.R., Woeginger, G.J., Bampis, E., Jansen, K. |
---|---|
Přispěvatelé: | Combinatorial Optimization 1 |
Jazyk: | angličtina |
Rok vydání: | 2010 |
Předmět: | |
Zdroj: | Approximation and Online Algorithms (7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers), 159-169 STARTPAGE=159;ENDPAGE=169;TITLE=Approximation and Online Algorithms (7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers) Approximation and Online Algorithms ISBN: 9783642124495 WAOA |
Popis: | 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 $\frac32$-approximation. Moreover, we further show that the best of these two solutions is a $\frac43$-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. |
Databáze: | OpenAIRE |
Externí odkaz: |