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.
翻译:在试图尽量扩大总效益的同时,将一组要素的所有要素完全对齐是一个复杂的问题。这种配对问题自然出现在科学、技术、经济学和其他领域的不同情况中。在上一份研究中,我们提出了一个有效的方法,在只有完全兼容性的制约下,推断各实体之间的基本兼容性。此外,通过将配对问题转化为与多层结构的旅行销售人员问题,一种配对优化算法被成功证明能够产生一种高度完全兼容的配对。然而,通过进一步利用基本数学特性来进一步提高性能,存在着很大的空间。在本研究中,我们证明在配对问题中存在代数结构。我们将最初估计的兼容性信息转化为一种等效形式,在这种形式中,个体兼容性的差异最小化。然后我们证明,在对已转变的问题使用对配算法时获得的总兼容性比以前的方法要高得多。在这种对配制问题上利用基本数学特性改进了观点后,我们可以促进无线通信等实际应用,例如无线通信超过5G,高效配对具有关键重要性。