IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v76y2012i2p223-237.html
   My bibliography  Save this article

Between a rock and a hard place: the two-to-one assignment problem

Author

Listed:
  • Dries Goossens
  • Sergey Polyakovskiy
  • Frits Spieksma
  • Gerhard Woeginger

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. Copyright Springer-Verlag 2012

Suggested Citation

  • Dries Goossens & Sergey Polyakovskiy & Frits Spieksma & Gerhard Woeginger, 2012. "Between a rock and a hard place: the two-to-one assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(2), pages 223-237, October.
    • Handle: RePEc:spr:mathme:v:76:y:2012:i:2:p:223-237
    DOI: 10.1007/s00186-012-0397-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-012-0397-2
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00186-012-0397-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Spieksma, Frits C. R. & Woeginger, Gerhard J., 1996. "Geometric three-dimensional assignment problems," European Journal of Operational Research, Elsevier, vol. 91(3), pages 611-618, June.
    2. Urban, Timothy L. & Russell, Robert A., 2003. "Scheduling sports competitions on multiple venues," European Journal of Operational Research, Elsevier, vol. 148(2), pages 302-311, July.
    3. Crama, Yves & Spieksma, Frits C. R., 1992. "Approximation algorithms for three-dimensional assignment problems with triangle inequalities," European Journal of Operational Research, Elsevier, vol. 60(3), pages 273-279, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zamorano, Emilio & Stolletz, Raik, 2017. "Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 55-68.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. H-J Bandelt & A Maas & F C R Spieksma, 2004. "Local search heuristics for multi-index assignment problems with decomposable costs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 694-704, July.
    2. Sergey Polyakovskiy & Frits C. R. Spieksma & Gerhard J. Woeginger, 2013. "The three-dimensional matching problem in Kalmanson matrices," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 1-9, July.
    3. Russell, Robert A. & Urban, Timothy L., 2010. "Multicriteria models for planning power-networking events," European Journal of Operational Research, Elsevier, vol. 207(1), pages 83-91, November.
    4. Huang, Edward & Mital, Pratik & Goetschalckx, Marc & Wu, Kan, 2016. "Optimal assignment of airport baggage unloading zones to outgoing flights," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 110-122.
    5. Walteros, Jose L. & Vogiatzis, Chrysafis & Pasiliao, Eduardo L. & Pardalos, Panos M., 2014. "Integer programming models for the multidimensional assignment problem with star costs," European Journal of Operational Research, Elsevier, vol. 235(3), pages 553-568.
    6. Jari Kyngäs & Kimmo Nurmi & Nico Kyngäs & George Lilley & Thea Salter & Dries Goossens, 2017. "Scheduling the Australian Football League," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 973-982, August.
    7. Steffen Borgwardt & Stephan Patterson, 2021. "On the computational complexity of finding a sparse Wasserstein barycenter," Journal of Combinatorial Optimization, Springer, vol. 41(3), pages 736-761, April.
    8. Simona Mancini, 2018. "Assignment of swimmers to events in a multi-team meeting for team global performance optimization," Annals of Operations Research, Springer, vol. 264(1), pages 325-337, May.
    9. P. Senthil Kumar, 2020. "Developing a New Approach to Solve Solid Assignment Problems Under Intuitionistic Fuzzy Environment," International Journal of Fuzzy System Applications (IJFSA), IGI Global, vol. 9(1), pages 1-34, January.
    10. Huang, Gaofeng & Lim, Andrew, 2006. "A hybrid genetic algorithm for the Three-Index Assignment Problem," European Journal of Operational Research, Elsevier, vol. 172(1), pages 249-257, July.
    11. Adam Farmer & Jeffrey S. Smith & Luke T. Miller, 2007. "Scheduling Umpire Crews for Professional Tennis Tournaments," Interfaces, INFORMS, vol. 37(2), pages 187-196, April.
    12. Mancini Simona & Isabello Andrea, 2014. "Fair referee assignment for the Italian soccer serieA," Journal of Quantitative Analysis in Sports, De Gruyter, vol. 10(2), pages 153-160, June.
    13. Spieksma, Frits C. R. & Woeginger, Gerhard J., 1996. "Geometric three-dimensional assignment problems," European Journal of Operational Research, Elsevier, vol. 91(3), pages 611-618, June.
    14. M B Wright, 2007. "Case study: problem formulation and solution for a real-world sports scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 439-445, April.
    15. M B Wright, 2009. "50 years of OR in sport," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 161-168, May.
    16. Carsten Gottschlich & Dominic Schuhmacher, 2014. "The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems," PLOS ONE, Public Library of Science, vol. 9(10), pages 1-10, October.
    17. Maurice Queyranne & Frits Spieksma & Fabio Tardella, 1998. "A General Class of Greedily Solvable Linear Programs," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 892-908, November.
    18. Urban, Timothy L. & Russell, Robert A., 2003. "Scheduling sports competitions on multiple venues," European Journal of Operational Research, Elsevier, vol. 148(2), pages 302-311, July.
    19. Renata M. Aiex & Mauricio G. C. Resende & Panos M. Pardalos & Gerardo Toraldo, 2005. "GRASP with Path Relinking for Three-Index Assignment," INFORMS Journal on Computing, INFORMS, vol. 17(2), pages 224-247, May.
    20. Boštjan Gabrovšek & Tina Novak & Janez Povh & Darja Rupnik Poklukar & Janez Žerovnik, 2020. "Multiple Hungarian Method for k -Assignment Problem," Mathematics, MDPI, vol. 8(11), pages 1-18, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:mathme:v:76:y:2012:i:2:p:223-237. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.