Cargando…
Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement
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 infe...
Autores principales: | , , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9858184/ https://www.ncbi.nlm.nih.gov/pubmed/36673287 http://dx.doi.org/10.3390/e25010146 |
_version_ | 1784874035441565696 |
---|---|
author | Fujita, Naoki Röhm, André Mihana, Takatomo Horisaki, Ryoichi Li, Aohan Hasegawa, Mikio Naruse, Makoto |
author_facet | Fujita, Naoki Röhm, André Mihana, Takatomo Horisaki, Ryoichi Li, Aohan Hasegawa, Mikio Naruse, Makoto |
author_sort | Fujita, Naoki |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-9858184 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-98581842023-01-21 Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement Fujita, Naoki Röhm, André Mihana, Takatomo Horisaki, Ryoichi Li, Aohan Hasegawa, Mikio Naruse, Makoto Entropy (Basel) Article 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. MDPI 2023-01-11 /pmc/articles/PMC9858184/ /pubmed/36673287 http://dx.doi.org/10.3390/e25010146 Text en © 2023 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Fujita, Naoki Röhm, André Mihana, Takatomo Horisaki, Ryoichi Li, Aohan Hasegawa, Mikio Naruse, Makoto Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title | Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title_full | Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title_fullStr | Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title_full_unstemmed | Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title_short | Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement |
title_sort | pairing optimization via statistics: algebraic structure in pairing problems and its application to performance enhancement |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9858184/ https://www.ncbi.nlm.nih.gov/pubmed/36673287 http://dx.doi.org/10.3390/e25010146 |
work_keys_str_mv | AT fujitanaoki pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT rohmandre pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT mihanatakatomo pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT horisakiryoichi pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT liaohan pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT hasegawamikio pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement AT narusemakoto pairingoptimizationviastatisticsalgebraicstructureinpairingproblemsanditsapplicationtoperformanceenhancement |