IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i11p2050-d446526.html
   My bibliography  Save this article

Multiple Hungarian Method for k -Assignment Problem

Author

Listed:
  • Boštjan Gabrovšek

    (Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
    Faculty of Mathematics and Physics, University of Ljubljana, Jadranska ulica 19, SI-1000 Ljubljana, Slovenia)

  • Tina Novak

    (Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia)

  • Janez Povh

    (Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
    Institute of Mathematics, Physics and Mechanics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia)

  • Darja Rupnik Poklukar

    (Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia)

  • Janez Žerovnik

    (Faculty of Mechanical Engineering, University of Ljubljana, Askerceva 6, SI-1000 Ljubljana, Slovenia
    Institute of Mathematics, Physics and Mechanics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia)

Abstract

The k -assignment problem (or, the k -matching problem) on k -partite graphs is an NP-hard problem for k ≥ 3 . In this paper we introduce five new heuristics. Two algorithms, B m and C m , arise as natural improvements of Algorithm A m from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, D m , E m , and F m , incorporate randomization. Algorithm D m can be considered as a greedy version of B m , whereas E m and F m are versions of local search algorithm, specialized for the k -matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm A m in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm A m ) to 0.08% over optimum (algorithm E m ). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm A m ) to 0.45% over optimum (algorithm F m ). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:11:p:2050-:d:446526
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/11/2050/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/11/2050/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Esther M. Arkin & Refael Hassin, 1998. "On Local Search for Weighted k -Set Packing," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 640-648, August.
    4. 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.
    5. Jingqun Li & R. Tharmarasa & Daly Brown & Thia Kirubarajan & Krishna R. Pattipati, 2019. "A novel convex dual approach to three-dimensional assignment problem: theoretical analysis," Computational Optimization and Applications, Springer, vol. 74(2), pages 481-516, November.
    6. 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.
    7. Egon Balas & Matthew J. Saltzman, 1991. "An Algorithm for the Three-Index Assignment Problem," Operations Research, INFORMS, vol. 39(1), pages 150-161, February.
    8. Frieze, A. M., 1983. "Complexity of a 3-dimensional assignment problem," European Journal of Operational Research, Elsevier, vol. 13(2), pages 161-164, June.
    9. H. W. Kuhn, 1955. "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2(1‐2), pages 83-97, March.
    10. Pentico, David W., 2007. "Assignment problems: A golden anniversary survey," European Journal of Operational Research, Elsevier, vol. 176(2), pages 774-793, January.
    11. Don A. Grundel & Pavlo A. Krokhmal & Carlos A. S. Oliveira & Panos M. Pardalos, 2007. "On the number of local minima for the multidimensional assignment problem," Journal of Combinatorial Optimization, Springer, vol. 13(1), pages 1-18, January.
    Full references (including those not matched with items on IDEAS)

    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. Kim, Bum-Jin & Hightower, William L. & Hahn, Peter M. & Zhu, Yi-Rong & Sun, Lu, 2010. "Lower bounds for the axial three-index assignment problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 654-668, May.
    2. 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.
    3. Jingqun Li & Thia Kirubarajan & R. Tharmarasa & Daly Brown & Krishna R. Pattipati, 2021. "A dual approach to multi-dimensional assignment problems," Journal of Global Optimization, Springer, vol. 81(3), pages 691-716, November.
    4. Krokhmal, Pavlo A. & Pardalos, Panos M., 2009. "Random assignment problems," European Journal of Operational Research, Elsevier, vol. 194(1), pages 1-17, April.
    5. Jingqun Li & R. Tharmarasa & Daly Brown & Thia Kirubarajan & Krishna R. Pattipati, 2019. "A novel convex dual approach to three-dimensional assignment problem: theoretical analysis," Computational Optimization and Applications, Springer, vol. 74(2), pages 481-516, November.
    6. 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.
    7. P. Senthil Kumar, 2020. "Algorithms for solving the optimization problems using fuzzy and intuitionistic fuzzy set," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 11(1), pages 189-222, February.
    8. Lev G. Afraimovich & Maxim D. Emelin, 2022. "Complexity of Solutions Combination for the Three-Index Axial Assignment Problem," Mathematics, MDPI, vol. 10(7), pages 1-10, March.
    9. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    10. Amit Kumar & Anila Gupta, 2013. "Mehar’s methods for fuzzy assignment problems with restrictions," Fuzzy Information and Engineering, Springer, vol. 5(1), pages 27-44, March.
    11. Yokoya, Daisuke & Duin, Cees W. & Yamada, Takeo, 2011. "A reduction approach to the repeated assignment problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 185-193, April.
    12. Talmor, Irit, 2022. "Solving the problem of maximizing diversity in public sector teams," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    13. Duc Manh Nguyen & Hoai An Le Thi & Tao Pham Dinh, 2014. "Solving the Multidimensional Assignment Problem by a Cross-Entropy method," Journal of Combinatorial Optimization, Springer, vol. 27(4), pages 808-823, May.
    14. 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.
    15. Christian Billing & Florian Jaehn & Thomas Wensing, 2020. "Fair task allocation problem," Annals of Operations Research, Springer, vol. 284(1), pages 131-146, January.
    16. 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.
    17. Don A. Grundel & Pavlo A. Krokhmal & Carlos A. S. Oliveira & Panos M. Pardalos, 2007. "On the number of local minima for the multidimensional assignment problem," Journal of Combinatorial Optimization, Springer, vol. 13(1), pages 1-18, January.
    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. Guojun Hu & Junran Lichen & Pengxiang Pan, 2023. "Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties," Mathematics, MDPI, vol. 11(24), pages 1-12, December.
    20. Prabhjot Kaur & Kalpana Dahiya & Vanita Verma, 2021. "Time-cost trade-off analysis of a priority based assignment problem," OPSEARCH, Springer;Operational Research Society of India, vol. 58(2), pages 448-482, June.

    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:gam:jmathe:v:8:y:2020:i:11:p:2050-:d:446526. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.