mlsanityData to 7 Oct 2026

Sublinear Time Algorithm for Online Weighted Bipartite Matching

arXiv 2208.03367 ↗First posted 5 Aug 2022cs.DS cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 35 of its 62 references that are in the map. First posted on arXiv 5 Aug 2022.

Builds on

35 of 62 references.

References · 35

  1. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  2. 2014Deep metric learning using Triplet networkcited by 421
  3. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  4. 2015Practical and Optimal LSH for Angular Distancecited by 105
  5. 2017Fast Matrix Factorization for Online Recommendation with Implicit Feedbackcited by 100
  6. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  7. 2021Faster Matchings via Learned Dualscited by 56
  8. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  9. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 45
  10. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  11. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  12. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
23 more
  1. 2013Beyond Locality-Sensitive Hashingcited by 23
  2. 2014On Symmetric and Asymmetric LSHs for Inner Product Searchcited by 23
  3. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  4. 2015Visual Search at Pinterestcited by 19
  5. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  6. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  7. 2021Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and Morecited by 15
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2019SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Searchcited by 12
  10. 2020Shop The Look: Building a Large Scale Visual Shopping System at Pinterestcited by 12
  11. 2022Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structurescited by 9
  12. 2020Edge-Weighted Online Bipartite Matchingcited by 8
  13. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  14. 2021Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Programcited by 5
  15. 2018Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Modelcited by 4
  16. 2018How to Match when All Vertices Arrive Onlinecited by 3
  17. 2018Approximate Nearest Neighbors in Limited Spacecited by 3
  18. 2019Online Matching with General Arrivalscited by 3
  19. 2019Beating Greedy for Stochastic Bipartite Matchingcited by 3
  20. 2016Semantic Similarity Strategies for Job Title Classificationcited by 2
  21. 2018Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeoutscited by 2
  22. 2018Online Submodular Maximization: Beating 1/2 Made Simplecited by 2
  23. 2020Fully Online Matching II: Beating Ranking and Water-fillingcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 4.

7 papers.

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  3. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  4. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  5. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  6. 2025HOFAR: High-Order Augmentation of Flow Autoregressive Transformerscited by 4
  7. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2