Fujita Naoki, Röhm André, Mihana Takatomo, Horisaki Ryoichi, Li Aohan, Hasegawa Mikio, Naruse Makoto
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.
Graduate School of Informatics and Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan.
Entropy (Basel). 2023 Jan 11;25(1):146. doi: 10.3390/e25010146.
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.
在尝试使总收益最大化的同时将集合中的所有元素完全配对是一个组合难题。此类配对问题自然出现在科学、技术、经济及其他领域的各种情形中。在我们之前的研究中，我们提出了一种有效方法，用于在仅能观测到总兼容性的约束下推断实体之间的潜在兼容性。此外，通过将配对问题转化为具有多层架构的旅行商问题，成功演示了一种配对优化算法，以得出高总兼容性的配对。然而，通过进一步利用潜在的数学性质，仍有很大的性能提升空间。在本研究中，我们证明了配对问题中代数结构的存在。我们将最初估计的兼容性信息转化为一种等效形式，其中个体兼容性的方差最小化。然后我们证明，在转换后的问题上使用启发式配对算法时获得的总兼容性比先前方法显著更高。借助这种利用基本数学性质对配对问题的改进观点，我们可以为诸如5G以上无线通信等实际应用做出贡献，在这些应用中高效配对至关重要。由于配对问题是最大加权匹配问题的特殊情况，我们的发现可能也对完全连通图上的其他算法有启示。
