Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity
复制标题
DOI：
10.1609/aaai.v33i01.33011877
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
中科院分区：
文献类型：
--
作者：
John P. Dickerson;Karthik Abinav Sankararaman;A. Srinivasan;Pan Xu
在二部匹配问题中，二部图一侧的顶点与另一侧的顶点配对。在它的在线版本中，图的一侧离线可用，而另一侧的顶点在线。当到达顶点时，算法应立即做出不可撤销的决策；要么将其匹配到一个可用的顶点，要么将其删除。这类问题的例子包括把工人和公司、广告商和关键词、器官和病人匹配起来，等等。许多文献关注的是通过匹配的总权重来最大化总相关性。然而，在许多现实问题中，考虑多样性的贡献也很重要：雇用不同的候选人，展示相关但不同的广告集，等等。在本文中，我们提出了在线子模二部匹配（OSBM）问题，其目标是在匹配边集合上最大化子模函数f。这个目标是足够普遍的，足以捕捉多样性（例如，加权覆盖函数）和相关性（例如，传统的线性函数）的概念，以及在实践中发生的许多其他自然目标函数（例如，广告设置的有限总预算）。我们提出了具有可证明保证的新算法，并且在限制于各种特殊情况时本质上是最优的。我们还在真实世界和合成数据集上运行实验来验证我们的算法。
In bipartite matching problems, vertices on one side of a bipartite graph are paired with those on the other. In its online variant, one side of the graph is available offline, while the vertices on the other side arrive online. When a vertex arrives, an irrevocable and immediate decision should be made by the algorithm; either match it to an available vertex or drop it. Examples of such problems include matching workers to firms, advertisers to keywords, organs to patients, and so on. Much of the literature focuses on maximizing the total relevance—modeled via total weight—of the matching. However, in many real-world problems, it is also important to consider contributions of diversity: hiring a diverse pool of candidates, displaying a relevant but diverse set of ads, and so on. In this paper, we propose the Online Submodular Bipartite Matching (OSBM) problem, where the goal is to maximize a submodular function f over the set of matched edges. This objective is general enough to capture the notion of both diversity (e.g., a weighted coverage function) and relevance (e.g., the traditional linear function)—as well as many other natural objective functions occurring in practice (e.g., limited total budget in advertising settings). We propose novel algorithms that have provable guarantees and are essentially optimal when restricted to various special cases. We also run experiments on real-world and synthetic datasets to validate our algorithms.