Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm
A many-to-many matching (MM) between two sets matches each element of one set to at least one element of the other set. A general case of the MM is the many-to-many matching with demands and capacities (MMDC) satisfying given lower and upper bounds on the number of elements matched to each element....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2023/7761902 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832559699784892416 |
|---|---|
| author | Fatemeh Rajabi-Alni Alireza Bagheri |
| author_facet | Fatemeh Rajabi-Alni Alireza Bagheri |
| author_sort | Fatemeh Rajabi-Alni |
| collection | DOAJ |
| description | A many-to-many matching (MM) between two sets matches each element of one set to at least one element of the other set. A general case of the MM is the many-to-many matching with demands and capacities (MMDC) satisfying given lower and upper bounds on the number of elements matched to each element. In this article, we give a polynomial-time algorithm for finding a minimum-cost MMDC between two sets using the well-known Hungarian algorithm. |
| format | Article |
| id | doaj-art-7668faa2ab4f456ea0b1fc2a1ee5a91c |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2023-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-7668faa2ab4f456ea0b1fc2a1ee5a91c2025-02-03T01:29:28ZengWileyJournal of Mathematics2314-47852023-01-01202310.1155/2023/7761902Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian AlgorithmFatemeh Rajabi-Alni0Alireza Bagheri1Computer Engineering DepartmentComputer Engineering DepartmentA many-to-many matching (MM) between two sets matches each element of one set to at least one element of the other set. A general case of the MM is the many-to-many matching with demands and capacities (MMDC) satisfying given lower and upper bounds on the number of elements matched to each element. In this article, we give a polynomial-time algorithm for finding a minimum-cost MMDC between two sets using the well-known Hungarian algorithm.http://dx.doi.org/10.1155/2023/7761902 |
| spellingShingle | Fatemeh Rajabi-Alni Alireza Bagheri Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm Journal of Mathematics |
| title | Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm |
| title_full | Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm |
| title_fullStr | Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm |
| title_full_unstemmed | Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm |
| title_short | Computing a Many-to-Many Matching with Demands and Capacities between Two Sets Using the Hungarian Algorithm |
| title_sort | computing a many to many matching with demands and capacities between two sets using the hungarian algorithm |
| url | http://dx.doi.org/10.1155/2023/7761902 |
| work_keys_str_mv | AT fatemehrajabialni computingamanytomanymatchingwithdemandsandcapacitiesbetweentwosetsusingthehungarianalgorithm AT alirezabagheri computingamanytomanymatchingwithdemandsandcapacitiesbetweentwosetsusingthehungarianalgorithm |