{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:45:00Z","timestamp":1760147100094,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T00:00:00Z","timestamp":1673395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJCR17N2","JP20H00233","JP22H05197"],"award-info":[{"award-number":["JPMJCR17N2","JP20H00233","JP22H05197"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JPMJCR17N2","JP20H00233","JP22H05197"],"award-info":[{"award-number":["JPMJCR17N2","JP20H00233","JP22H05197"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JPMJCR17N2","JP20H00233","JP22H05197"],"award-info":[{"award-number":["JPMJCR17N2","JP20H00233","JP22H05197"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Fully pairing all elements of a set while attempting to maximize the total benefit is a combinatorically difficult problem. Such pairing problems naturally appear in various situations in science, technology, economics, and other fields. In our previous study, we proposed an efficient method to infer the underlying compatibilities among the entities, under the constraint that only the total compatibility is observable. Furthermore, by transforming the pairing problem into a traveling salesman problem with a multi-layer architecture, a pairing optimization algorithm was successfully demonstrated to derive a high-total-compatibility pairing. However, there is substantial room for further performance enhancement by further exploiting the underlying mathematical properties. In this study, we prove the existence of algebraic structures in the pairing problem. We transform the initially estimated compatibility information into an equivalent form where the variance of the individual compatibilities is minimized. We then demonstrate that the total compatibility obtained when using the heuristic pairing algorithm on the transformed problem is significantly higher compared to the previous method. With this improved perspective on the pairing problem using fundamental mathematical properties, we can contribute to practical applications such as wireless communications beyond 5G, where efficient pairing is of critical importance. As the pairing problem is a special case of the maximum weighted matching problem, our findings may also have implications for other algorithms on fully connected graphs.<\/jats:p>","DOI":"10.3390\/e25010146","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T06:18:08Z","timestamp":1673417888000},"page":"146","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6332-5975","authenticated-orcid":false,"given":"Naoki","family":"Fujita","sequence":"first","affiliation":[{"name":"Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8552-7922","authenticated-orcid":false,"given":"Andr\u00e9","family":"R\u00f6hm","sequence":"additional","affiliation":[{"name":"Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4390-710X","authenticated-orcid":false,"given":"Takatomo","family":"Mihana","sequence":"additional","affiliation":[{"name":"Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2280-5921","authenticated-orcid":false,"given":"Ryoichi","family":"Horisaki","sequence":"additional","affiliation":[{"name":"Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0618-4894","authenticated-orcid":false,"given":"Aohan","family":"Li","sequence":"additional","affiliation":[{"name":"Graduate School of Informatics and Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5638-8022","authenticated-orcid":false,"given":"Mikio","family":"Hasegawa","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Faculty of Engineering, Tokyo University of Science, 6-3-1 Niijuku, Katsushika-ku, Tokyo 125-8585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8982-9824","authenticated-orcid":false,"given":"Makoto","family":"Naruse","sequence":"additional","affiliation":[{"name":"Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Am. Math. Mon."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1287\/moor.7.4.617","article-title":"The economics of matching: Stability and incentives","volume":"7","author":"Roth","year":"1982","journal-title":"Math. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1645","DOI":"10.3982\/ECTA13971","article-title":"Dual-Donor Organ Exchange","volume":"85","author":"Ergin","year":"2017","journal-title":"Econometrica"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1023\/B:ANOR.0000019091.54417.ca","article-title":"Airline crew rostering: Problem types, modeling, and optimization","volume":"127","author":"Kohl","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41534-016-0004-0","article-title":"Building logical qubits in a superconducting quantum computing system","volume":"3","author":"Gambetta","year":"2017","journal-title":"npj Quantum Inf."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.image.2010.10.006","article-title":"3D model retrieval using weighted bipartite graph matching","volume":"26","author":"Gao","year":"2011","journal-title":"Signal Process. Image Commun."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bellur, U., and Kulkarni, R. (2007, January 9\u201313). Improved matchmaking algorithm for semantic web services based on bipartite graph matching. Proceedings of the IEEE International Conference on Web Services (ICWS 2007), Salt Lake City, UT, USA.","DOI":"10.1109\/ICWS.2007.105"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"ref_9","unstructured":"Gabow, H.N. (1990, January 22\u201324). Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Huang, C.C., and Kavitha, T. (2012, January 17\u201319). Efficient algorithms for maximum weight matchings in general graphs with small edge weights. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.110"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1016\/j.ipl.2012.08.010","article-title":"A simple reduction from maximum weight matching to maximum cardinality matching","volume":"112","author":"Pettie","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2736283","article-title":"Algorithmic applications of baur-strassen\u2019s theorem: Shortest cycles, diameter, and matchings","volume":"62","author":"Cygan","year":"2015","journal-title":"J. ACM (JACM)"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Duan, R., and Pettie, S. (2010, January 23\u201326). Approximating maximum weight matching in near-linear time. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.70"},{"key":"ref_14","unstructured":"Hanke, S., and Hougardy, S. (2023, January 10). New Approximation Algorithms for the Weighted Matching Problem. Citeseer. Available online: https:\/\/citeseerx.ist.psu.edu\/document?repid=rep1&type=pdf&doi=f6bc65fe193c8afd779f2867831a869c59554661."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2529989","article-title":"Linear-time approximation for maximum weight matching","volume":"61","author":"Duan","year":"2014","journal-title":"J. Acm (JACM)"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/j.ins.2022.10.021","article-title":"Solving maximum weighted matching on large graphs with deep reinforcement learning","volume":"614","author":"Wu","year":"2022","journal-title":"Inf. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"57630","DOI":"10.1109\/ACCESS.2022.3179113","article-title":"Efficient Pairing in Unknown Environments: Minimal Observations and TSP-based Optimization","volume":"10","author":"Fujita","year":"2022","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Williams, V.V. (2012, January 20\u201322). Multiplying matrices faster than Coppersmith-Winograd. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214056"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02186476","article-title":"The auction algorithm: A distributed relaxation method for the assignment problem","volume":"14","author":"Bertsekas","year":"1988","journal-title":"Ann. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1137\/0105003","article-title":"Algorithms for the assignment and transportation problems","volume":"5","author":"Munkres","year":"1957","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Goldberg, A., and Radzik, T. (1993). A Heuristic Improvement of the Bellman-Ford Algorithm, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE. Technical Report.","DOI":"10.1016\/0893-9659(93)90022-F"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"9713450","DOI":"10.1155\/2018\/9713450","article-title":"A tutorial on nonorthogonal multiple access for 5G and beyond","volume":"2018","author":"Aldababsa","year":"2018","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6010","DOI":"10.1109\/TVT.2015.2480766","article-title":"Impact of user pairing on 5G nonorthogonal multiple-access downlink transmissions","volume":"65","author":"Ding","year":"2015","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"19602","DOI":"10.1109\/ACCESS.2019.2896181","article-title":"Proportional fairness-based user pairing and power allocation algorithm for non-orthogonal multiple access system","volume":"7","author":"Chen","year":"2019","journal-title":"IEEE Access"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1109\/OJITS.2021.3107347","article-title":"Optimizing resource allocation for 6G NOMA-enabled cooperative vehicular networks","volume":"2","author":"Ali","year":"2021","journal-title":"IEEE Open J. Intell. Transp. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1375","DOI":"10.1109\/TCOMM.2020.3037597","article-title":"Energy efficient resource allocation in terahertz downlink NOMA systems","volume":"69","author":"Zhang","year":"2020","journal-title":"IEEE Trans. Commun."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2884","DOI":"10.1002\/wcm.2736","article-title":"User pairing schemes for capacity maximization in non-orthogonal multiple access systems","volume":"16","author":"Shahab","year":"2016","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1109\/LWC.2018.2853741","article-title":"Optimal user pairing for downlink non-orthogonal multiple access (NOMA)","volume":"8","author":"Zhu","year":"2018","journal-title":"IEEE Wirel. Commun. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1587\/transcom.E98.B.403","article-title":"Non-orthogonal multiple access (NOMA) with successive interference cancellation for future radio access","volume":"98","author":"Higuchi","year":"2015","journal-title":"IEICE Trans. Commun."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s11831-017-9247-y","article-title":"Combinatorial optimization: Comparison of heuristic algorithms in travelling salesman problem","volume":"26","author":"Halim","year":"2019","journal-title":"Arch. Comput. Methods Eng."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/6462.6502","article-title":"Efficient algorithms for finding maximum matching in graphs","volume":"18","author":"Galil","year":"1986","journal-title":"ACM Comput. Surv. (CSUR)"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/146\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:03:08Z","timestamp":1760119388000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/1\/146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,11]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["e25010146"],"URL":"https:\/\/doi.org\/10.3390\/e25010146","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,1,11]]}}}