An Algorithm for Multi-Attribute Diverse Matching
Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application.
Code (0)
등록된 구현이 없습니다.
Tasks
AttributeDiversitySimilar Papers 제목 키워드 기반
Multi-Intent Attribute-Aware Text Matching in Searching
Text matching systems have become a fundamental service in most searching platforms. For instance, they are responsible for matching user queries to relevant candidate items, or rewriting the user-input query to a pre-se…
AttributeText MatchingFast Redescription Mining Using Locality-Sensitive Hashing
Redescription mining is a data analysis technique that has found applications in diverse fields. The most used redescription mining approaches involve two phases: finding matching pairs among data attributes and extendin…
Heterogeneous Entity Matching with Complex Attribute Associations using BERT and Neural Networks
Across various domains, data from different sources such as Baidu Baike and Wikipedia often manifest in distinct forms. Current entity matching methodologies predominantly focus on homogeneous data, characterized by attr…
AttributeExploiting Multi-layer Graph Factorization for Multi-attributed Graph Matching
Multi-attributed graph matching is a problem of finding correspondences between two sets of data while considering their complex properties described in multiple attributes. However, the information of multiple attribute…
AttributeGraph MatchingMARS: Matching Attribute-aware Representations for Text-based Sequential Recommendation
Sequential recommendation aims to predict the next item a user is likely to prefer based on their sequential interaction history. Recently, text-based sequential recommendation has emerged as a promising paradigm that us…
AttributeSequential RecommendationTransfer Learning