On the maximum edge-pair embedding bipartite matching

Given a set of edge pairs in a complete bipartite graph, we want to find a bipartite matching that includes the maximum number of those edge pairs. While the problem has many applications to wireless localization and computer vision, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless , we show that there is no constant approximation for the problem. Then, we consider two special cases of the problem. Suppose that denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, the first case is for when is not large. While there is a simple polynomial-time algorithm for the problem when is one, we show that the problem is NP-hard when is greater than one. We also devise an efficient -approximation algorithm for the problem. For the second case, every pair of nodes in the same partition of the input bipartite graph are labeled with one of colors. We want to match, between the two partitions, a pair of nodes to a pair of nodes with the same color. Denote as the number of nodes, we give an -approximation algorithm for this case.