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)

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Approximation for Unpopularity in (3, 3)-Hypergraph Matching with One-Sided Preferences

  • Yashdeep Singh,
  • Sushanta Karmakar

摘要

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)