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 decide 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.
翻译：在线双面匹配是在线算法中的一个基本问题。 目标是匹配两组脊椎, 以最大化边缘重量的总和, 其中一组脊椎、 每一个脊椎及其相应的边缘重量会按顺序出现。 目前, 在实用建议系统或搜索引擎中, 加权是由内产物决定的, 即用户的深度表示和某个项目的深度表示。 标准的在线匹配需要支付美元时间, 以线性扫描所有项目, 计算重量( 假设每个代表矢量的长度为$d$), 然后根据重量来决定匹配。 然而, 在现实中, 美元可能非常大, 比如在在线电子商务平台中。 因此, 改善计算重量的时间是一个具有实际意义的问题 。 在这项工作中, 我们提供了计算重量的理论基础 。 我们通过我们提议的随机化数据结构, 重量可以在亚线性时间里计算, 同时保持匹配算法的竞争性比 。
相关内容
微信扫码咨询专知VIP会员