Improved Approximation for Unpopularity in (3, 3)-Hypergraph Matching with One-Sided Preferences
摘要
Given two sets of distinct items and a group of people with combined preferences for one item from each set, how can we optimally assign pairs of items to individuals? To solve this problem, we examine the popular matching problem in a 3-uniform 3-partite hypergraph. Here, the first set represents agents, whereas the second and third sets correspond to two different types of items. Agents express preferences over hyperedges, whereas the items in the other sets do not have any preferences. A matching M is considered popular if there is no alternative matching $$M'$$ such that more agents prefer $$M'$$ to matching M. Finding a popular matching, if it exists, is computationally hard. In such a case, an approximation is required. A common measure for such an approximation is called the unpopularity factor for a matching M, denoted as u(M). It is defined as the largest ratio $$|A_2|/|A_1|$$ , where $$A_1$$ represents the set of agents who prefer matching M over any other $$M'$$ , and $$A_2$$ represents the set of agents who prefer $$M'$$ over M. In this paper, we provide an approximation algorithm that produces a 3-uniform 3-partite hypergraph matching M such that $$u(M)\le d^2$$ where d is the maximum degree of an agent. This work improves on a previously known result in the same hypergraph model, where the unpopularity factor was bounded by $$1.5 \times 3^{\frac{d}{2}}$$ . Furthermore, we also show that $$u(M)