  Generating paired sequences with maximal compatibility from a given set is
one of the most important challenges in various applications, including
information and communication technologies. However, the number of possible
pairings explodes in a double factorial order as a function of the number of
entities, manifesting the difficulties of finding the optimal pairing that
maximizes the overall reward. In the meantime, in real-world systems, such as
user pairing in non-orthogonal multiple access (NOMA), pairing often needs to
be conducted at high speed in dynamically changing environments; hence,
efficient recognition of the environment and finding high reward pairings are
highly demanded. In this paper, we demonstrate an efficient pairing algorithm
to recognize compatibilities among elements as well as to find a pairing that
yields a high total compatibility. The proposed pairing strategy consists of
two phases. The first is the observation phase, where compatibility information
among elements is obtained by only observing the sum of rewards. We show an
efficient strategy that allows obtaining all compatibility information with
minimal observations. The minimum number of observations under these conditions
is also discussed, along with its mathematical proof. The second is the
combination phase, by which a pairing with a large total reward is determined
heuristically. We transform the pairing problem into a traveling salesman
problem (TSP) in a three-layer graph structure, which we call Pairing-TSP. We
demonstrate heuristic algorithms in solving the Pairing-TSP efficiently. This
research is expected to be utilized in real-world applications such as NOMA,
social networks, among others.

Data Structures and Algorithms;Systems and Control;Systems and Control;Optimization and Control