Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic

Gonzague Yernaux; Mikel Vandeloise; Manel Barkallah; Wim Vanhoof; Jean-Marie Jacquet

doi:10.1007/978-3-031-87647-9_5

Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic

Gonzague Yernaux, Mikel Vandeloise, Manel Barkallah, Wim Vanhoof, Jean-Marie Jacquet

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Conference contribution

1 Downloads (Pure)

Abstract

Bipartite matching problems play a crucial role in various software engineering tools, including resource allocation and task assignment. In this paper, we address a specific variant of the bipartite matching problem, called the Double Assignment Problem (DAP), focusing on the allocation of machines to workers in a production environment. The objective is to maximize the number of worker-machine associations, subject to a second, orthogonal matching problem: associating some worker W to a machine M implies that the (ordered) list of servers employed by M are dedicated to the respective programs used by the worker W. Since DAP is, in general, NP-hard, we introduce a heuristic that quickly approximates candidate results. The heuristic is called k-swap stability and has originally been formalized to tackle a specific DAP instance arising in the niche field of anti-unification. We extend the definition to our more general setting and give promising preliminary results obtained by applying our k-swap implementation on a testbed of examples.

Original language	English
Title of host publication	Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025
Subtitle of host publication	Proceedings of the Third International Conference on Advances in Computing Research (ACR’25)
Editors	Kevin Daimi, Abeer Al Sadoon
Publisher	Springer, Cham
Pages	51-62
Number of pages	12
Volume	1346
ISBN (Electronic)	978-3-031-87647-9
ISBN (Print)	978-3-031-87646-2
DOIs	https://doi.org/10.1007/978-3-031-87647-9_5
Publication status	Published - Apr 2025

Publication series

Name	Lecture Notes in Networks and Systems
Volume	1346 LNNS
ISSN (Print)	2367-3370
ISSN (Electronic)	2367-3389

Keywords

Double Assignment Problem
Combinatorial optimization
Approximation algorithms
Escape game puzzles
Resource allocation
combinatorial optimization
resource allocation
escape game puzzles
approximation algorithms

Access to Document

10.1007/978-3-031-87647-9_5

ACR2991Accepted author manuscript, 2.98 MBLicence: Unspecified
2025ACR-DAPFinal published version, 1.81 MBLicence: Unspecified

Cite this

Yernaux, G., Vandeloise, M., Barkallah, M., Vanhoof, W., & Jacquet, J.-M. (2025). Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic. In K. Daimi, & A. Al Sadoon (Eds.), Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025: Proceedings of the Third International Conference on Advances in Computing Research (ACR’25) (Vol. 1346, pp. 51-62). (Lecture Notes in Networks and Systems; Vol. 1346 LNNS). Springer, Cham. https://doi.org/10.1007/978-3-031-87647-9_5

Yernaux, Gonzague ; Vandeloise, Mikel ; Barkallah, Manel et al. / Optimizing Bipartite Matching with Interleaved and Injective Mappings : Implementing and Evaluating the k-swap Heuristic. Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025: Proceedings of the Third International Conference on Advances in Computing Research (ACR’25). editor / Kevin Daimi ; Abeer Al Sadoon. Vol. 1346 Springer, Cham, 2025. pp. 51-62 (Lecture Notes in Networks and Systems).

@inproceedings{f5792850a91841b7ad9fbfabcc8a358c,

title = "Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic",

abstract = "Bipartite matching problems play a crucial role in various software engineering tools, including resource allocation and task assignment. In this paper, we address a specific variant of the bipartite matching problem, called the Double Assignment Problem (DAP), focusing on the allocation of machines to workers in a production environment. The objective is to maximize the number of worker-machine associations, subject to a second, orthogonal matching problem: associating some worker W to a machine M implies that the (ordered) list of servers employed by M are dedicated to the respective programs used by the worker W. Since DAP is, in general, NP-hard, we introduce a heuristic that quickly approximates candidate results. The heuristic is called k-swap stability and has originally been formalized to tackle a specific DAP instance arising in the niche field of anti-unification. We extend the definition to our more general setting and give promising preliminary results obtained by applying our k-swap implementation on a testbed of examples.",

keywords = "Double Assignment Problem, Combinatorial optimization, Approximation algorithms, Escape game puzzles, Resource allocation, combinatorial optimization, resource allocation, escape game puzzles, approximation algorithms",

author = "Gonzague Yernaux and Mikel Vandeloise and Manel Barkallah and Wim Vanhoof and Jean-Marie Jacquet",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.",

year = "2025",

month = apr,

doi = "10.1007/978-3-031-87647-9_5",

language = "English",

isbn = "978-3-031-87646-2",

volume = "1346",

series = "Lecture Notes in Networks and Systems",

publisher = "Springer, Cham",

pages = "51--62",

editor = "Kevin Daimi and {Al Sadoon}, {Abeer }",

booktitle = "Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025",

}

Yernaux, G , Vandeloise, M , Barkallah, M , Vanhoof, W & Jacquet, J-M 2025, Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic. in K Daimi & A Al Sadoon (eds), Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025: Proceedings of the Third International Conference on Advances in Computing Research (ACR’25). vol. 1346, Lecture Notes in Networks and Systems, vol. 1346 LNNS, Springer, Cham, pp. 51-62. https://doi.org/10.1007/978-3-031-87647-9_5

Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic. / Yernaux, Gonzague ; Vandeloise, Mikel ; Barkallah, Manel et al.
Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025: Proceedings of the Third International Conference on Advances in Computing Research (ACR’25). ed. / Kevin Daimi; Abeer Al Sadoon. Vol. 1346 Springer, Cham, 2025. p. 51-62 (Lecture Notes in Networks and Systems; Vol. 1346 LNNS).

Research output: Contribution in Book/Catalog/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Optimizing Bipartite Matching with Interleaved and Injective Mappings

T2 - Implementing and Evaluating the k-swap Heuristic

AU - Yernaux, Gonzague

AU - Vandeloise, Mikel

AU - Barkallah, Manel

AU - Vanhoof, Wim

AU - Jacquet, Jean-Marie

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025/4

Y1 - 2025/4

N2 - Bipartite matching problems play a crucial role in various software engineering tools, including resource allocation and task assignment. In this paper, we address a specific variant of the bipartite matching problem, called the Double Assignment Problem (DAP), focusing on the allocation of machines to workers in a production environment. The objective is to maximize the number of worker-machine associations, subject to a second, orthogonal matching problem: associating some worker W to a machine M implies that the (ordered) list of servers employed by M are dedicated to the respective programs used by the worker W. Since DAP is, in general, NP-hard, we introduce a heuristic that quickly approximates candidate results. The heuristic is called k-swap stability and has originally been formalized to tackle a specific DAP instance arising in the niche field of anti-unification. We extend the definition to our more general setting and give promising preliminary results obtained by applying our k-swap implementation on a testbed of examples.

AB - Bipartite matching problems play a crucial role in various software engineering tools, including resource allocation and task assignment. In this paper, we address a specific variant of the bipartite matching problem, called the Double Assignment Problem (DAP), focusing on the allocation of machines to workers in a production environment. The objective is to maximize the number of worker-machine associations, subject to a second, orthogonal matching problem: associating some worker W to a machine M implies that the (ordered) list of servers employed by M are dedicated to the respective programs used by the worker W. Since DAP is, in general, NP-hard, we introduce a heuristic that quickly approximates candidate results. The heuristic is called k-swap stability and has originally been formalized to tackle a specific DAP instance arising in the niche field of anti-unification. We extend the definition to our more general setting and give promising preliminary results obtained by applying our k-swap implementation on a testbed of examples.

KW - Double Assignment Problem

KW - Combinatorial optimization

KW - Approximation algorithms

KW - Escape game puzzles

KW - Resource allocation

KW - combinatorial optimization

KW - resource allocation

KW - escape game puzzles

KW - approximation algorithms

UR - http://www.scopus.com/inward/record.url?scp=105003623449&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-87647-9_5

DO - 10.1007/978-3-031-87647-9_5

M3 - Conference contribution

SN - 978-3-031-87646-2

VL - 1346

T3 - Lecture Notes in Networks and Systems

SP - 51

EP - 62

BT - Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025

A2 - Daimi, Kevin

A2 - Al Sadoon, Abeer

PB - Springer, Cham

ER -

Yernaux G , Vandeloise M , Barkallah M , Vanhoof W , Jacquet JM. Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic. In Daimi K, Al Sadoon A, editors, Proceedings of the 3rd International Conference on Advances in Computing Research, ACR 2025: Proceedings of the Third International Conference on Advances in Computing Research (ACR’25). Vol. 1346. Springer, Cham. 2025. p. 51-62. (Lecture Notes in Networks and Systems). doi: 10.1007/978-3-031-87647-9_5

Optimizing Bipartite Matching with Interleaved and Injective Mappings: Implementing and Evaluating the k-swap Heuristic

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Algorithmic equivalence by generalization-driven transformations of logic programs