论文标题
用于在线加权双方匹配的司额时间算法
Sublinear Time Algorithm for Online Weighted Bipartite Matching
论文作者
论文摘要
在线二手匹配是在线算法中的一个基本问题。目的是匹配两组顶点，以最大化边缘权重的总和，在该顶点中，对于一组顶点，每个顶点及其相应的边缘权重以一个顺序出现。当前，在实际的推荐系统或搜索引擎中，权重是由用户的深度表示与项目深度表示之间的内部产品决定的。标准的在线匹配需要支付$ nd $时间来线性扫描所有$ n $项目，计算重量（假设每个表示向量都有长度$ d $），然后根据权重决定匹配。但是，实际上，$ n $可能非常大，例如在在线电子商务平台中。因此，改善计算权重的时间是一个实践意义的问题。在这项工作中，我们为大约计算权重的理论基础提供了基础。我们表明，借助我们提出的随机数据结构，可以在均匀时间内计算权重，同时仍保留匹配算法的竞争比率。
Online bipartite matching is a fundamental problem in online algorithms. The goal is to match two sets of vertices to maximize the sum of the edge weights, where for one set of vertices, each vertex and its corresponding edge weights appear in a sequence. Currently, in the practical recommendation system or search engine, the weights are decided by the inner product between the deep representation of a user and the deep representation of an item. The standard online matching needs to pay $nd$ time to linear scan all the $n$ items, computing weight (assuming each representation vector has length $d$), and then deciding the matching based on the weights. However, in reality, the $n$ could be very large, e.g. in online e-commerce platforms. Thus, improving the time of computing weights is a problem of practical significance. In this work, we provide the theoretical foundation for computing the weights approximately. We show that, with our proposed randomized data structures, the weights can be computed in sublinear time while still preserving the competitive ratio of the matching algorithm.
