Sublinear Time Algorithm for Online Weighted Bipartite Matching
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914675071909888 |
|---|---|
| author | Hu, Hang Song, Zhao Tao, Runzhou Xu, Zhaozhuo Yin, Junze Zhuo, Danyang |
| author_facet | Hu, Hang Song, Zhao Tao, Runzhou Xu, Zhaozhuo Yin, Junze Zhuo, Danyang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_03367 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sublinear Time Algorithm for Online Weighted Bipartite Matching Hu, Hang Song, Zhao Tao, Runzhou Xu, Zhaozhuo Yin, Junze Zhuo, Danyang Data Structures and Algorithms Machine Learning 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. |
| title | Sublinear Time Algorithm for Online Weighted Bipartite Matching |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2208.03367 |