Optimally stable matchings for resource allocations
Author affiliations
DOI:
https://doi.org/10.15625/2525-2518/16107Keywords:
stable marriage, integer linear programming (ILP), resource allocation, network computtingAbstract
The stable marriage problem (SMP) and its variants have received much attention in the literature due to their wide range of applications. One of their applications is resource allocation in network environments. In this paper, we consider two resource allocation problems. The first one is to maximize the performance of a system in the fog computing environment while maintaining a low cost. In the problem, the resource allocation task will be rewritten as the MAX-SMTI variant (i.e., finding the maximum cardinality stable matching of the stable marriage with ties and incomplete lists). It is then formulated under an integer linear program to solve. The best allocation can then be chosen to be the lowest cost one among stable matchings. In the same manner, another variant called MAX-HRT (i.e., finding the maximum cardinality stable matching of the hospital-residents with ties) is applied for the second application regarding the virtual machine allocation. By using MAX-SMTI and MAX-HRT models which are solved via integer linear programs, we aim to not only find stable matchings for the resource allocation problems but also maximum length matchings. Consequently, a maximum number of user requests should be served at a time. The models are implemented in C++ using the SCIP solver. Numerical experiments are conducted for large datasets and results are given to show the efficiency of the models.
Downloads
References
Abraham D. J., Irving R. W. and Manlove D. F. - The student-project allocation problem, in Proceedings of the 14th International Symposium, Kyoto, Japan, Dec. 2003, pp. 474–484. DOI: https://doi.org/10.1007/978-3-540-24587-2_49
Battula S. K., Garg S., Naha R. K., Thulasiraman P. and Thulasiram R. - A micro-level compensation-based cost model for resource allocation in a fog environment, Sensors 19 (13) (2019) 2954. DOI: https://doi.org/10.3390/s19132954
Chu Q., Cui L. and Zhang Y. - Joint Computing and Storage Resource Allocation Based on Stable Matching in Data Centers, IEEE 3rd international conference on big data security on cloud, 2017, pp. 207-212. DOI: https://doi.org/10.1109/BigDataSecurity.2017.36
Delorme M., García S., Gondzio J., Kalcsics J., Manlove D. F., and Pettersson W. - Mathematical models for stable matching problems with ties and incomplete lists, European Journal of Operational Research 277 (2) (2019) 426-441. DOI: https://doi.org/10.1016/j.ejor.2019.03.017
Fleiner T., Irving R. W., and Manlove D. F. - Efficient algorithms for generalized stable marriage and roommates problems, Theoretical Computer Science 381 (1-3) (2007) 162-176. DOI: https://doi.org/10.1016/j.tcs.2007.04.029
Gale D. and Shapley L. S. - College admissions and the stability of marriage, The American Mathematical Monthly 9 (1) (1962) 9-15. DOI: https://doi.org/10.1080/00029890.1962.11989827
Gelain M., Pini M. S., Rossi F., Venable K. B. and Walsh T. - Local search approaches in stable matching problems, Algorithms 6 (1) (2013) 591-617. DOI: https://doi.org/10.3390/a6040591
Gent I. P. and Prosser P. - An empirical study of the stable marriage problem with ties and incomplete lists, Proceedings of the 15th European Conference on Artificial Intelligence, Lyon, France, Jul. 2002, pp. 141-145.
Gusfield D. and Irving R. W. - The stable marriage problem: structure and algorithms, MIT Press Cambridge, 1989.
Irving R. W. - An efficient algorithm for the “stable roommates” problem, Journal of Algorithms 6 (1)(1985) 577-595. DOI: https://doi.org/10.1016/0196-6774(85)90033-1
Kim G. and Lee W. - Stable matching with ties for cloud-assisted smart tv services,Proceedings of the 2014 IEEE International Conference on Consumer Electronics (ICCE), 2014, pp. 558–559. DOI: https://doi.org/10.1109/ICCE.2014.6776132
Kiraly Z. - Linear time local approximation algorithm for maximum stable marriage, Algorithms, 6 (3) (2013) 4. DOI: https://doi.org/10.3390/a6030471
Kishk S., Almofari N. H., and Zaki F.W. - Distributed resource allocation in D2D communication networks with energy harvesting relays using stable matching, Ad Hoc Networks 61 (2017) 114-123. DOI: https://doi.org/10.1016/j.adhoc.2017.03.010
Kwanashie A. andManlove D. F. - An integer programming approach to the hospitals/residents problem with ties, Operations Research Proceedings, 2014, pp. 263-269. DOI: https://doi.org/10.1007/978-3-319-07001-8_36
Manlove D. F., Irving R. W., Iwama M., Miyazaki S., and Morita Y. - Hard variants of stable marriage, Theoretical Computer Science, 276 (1-2) (2002) 261-279. DOI: https://doi.org/10.1016/S0304-3975(01)00206-7
McDermid E. J. - A 3/2-approximation algorithm for general stable marriage,Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), 2009, pp. 689-700. DOI: https://doi.org/10.1007/978-3-642-02927-1_57
Munera D., Diaz D., Abreu S., Rossi F., Saraswat V. and Codognet P. - Solving hard stable matching problems via local search and cooperative parallelization, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, Texas, Jan. 2015, pp. 1212-1218. DOI: https://doi.org/10.1609/aaai.v29i1.9360
Naha R. K., Garg S. and Chan A. - Big Data-Enabled Internet of Things, Institution of Engineering and Technology (IET) Digital Library, Fog-computing architecture: survey and challenges, 2019, pp. 199-224. DOI: https://doi.org/10.1049/PBPC025E_ch10
Roth A. E. - The evolution of the labor market for medical interns and residents: A case study in game theory, Journal of Political Economy 92 (6) (1984) 991-1016. DOI: https://doi.org/10.1086/261272
Vate J. H. V. - Linear programming brings marital bliss, Operations Research Letters 8 (3) (1989) 147-153. DOI: https://doi.org/10.1016/0167-6377(89)90041-2
Viet H. H., Uyen N. T., Lee S. G.,Chung T. C., and Trang L. H. - Amax conflictsbasedheuristic search for the stable marriage problem with ties and incomplete lists, Journal of Heuristics 27 (2021) 439-458. DOI: https://doi.org/10.1007/s10732-020-09464-8
Wang J. V., Fok K., Cheng C., and Tse C. K. - A stable matching-based virtualmachine allocation mechanism for cloud data centers,IEEE World Congress onServices, 2016, pp. 103-106. DOI: https://doi.org/10.1109/SERVICES.2016.21
Long D. T. - An enhanced genetic algorithm-based courses timetabling method for maximal enrollments using maximum matching on bipartite graphs, Vietnam Journal of Science and Technology 57 (6) (2019) 734-748. DOI: https://doi.org/10.15625/2525-2518/57/6/13501
Xu H. and Li B. - Egalitarian stable matching for VM migration in cloud computing, Proceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2011, pp. 631-636. DOI: https://doi.org/10.1109/INFCOMW.2011.5928889
Zhou Z., Gao C., Xu C., Chen T., Zhang D. and Mumtaz S. - Energy-Efficient Stable Matching for Resource Allocation in Energy Harvesting-Based Device-to-Device Communications, IEEE Access 5 (2017) 15184-15196. DOI: https://doi.org/10.1109/ACCESS.2017.2678508
Toan P. T. and Loc N. T. - A branch and bound algorithm for workflow scheduling, Vietnam Journal of Science and Technology 56 (2) (2018) 246-256. DOI: https://doi.org/10.15625/2525-2518/56/2/10672
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Vietnam Journal of Sciences and Technology (VJST) is an open access and peer-reviewed journal. All academic publications could be made free to read and downloaded for everyone. In addition, articles are published under term of the Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA) Licence which permits use, distribution and reproduction in any medium, provided the original work is properly cited & ShareAlike terms followed.
Copyright on any research article published in VJST is retained by the respective author(s), without restrictions. Authors grant VAST Journals System a license to publish the article and identify itself as the original publisher. Upon author(s) by giving permission to VJST either via VJST journal portal or other channel to publish their research work in VJST agrees to all the terms and conditions of https://creativecommons.org/licenses/by-sa/4.0/ License and terms & condition set by VJST.
Authors have the responsibility of to secure all necessary copyright permissions for the use of 3rd-party materials in their manuscript.
Vietnam Journal of Science and Technology (VJST) is pleased to notice: