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...

Descripción completa

Detalles Bibliográficos
Autores principales: Fujita, Naoki, Röhm, André, Mihana, Takatomo, Horisaki, Ryoichi, Li, Aohan, Hasegawa, Mikio, Naruse, Makoto
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