# Sublinear Time Algorithm for Online Weighted Bipartite Matching

arXiv: https://arxiv.org/abs/2208.03367 · HTML: https://mlsanity.com/paper/2208.03367/

## Key facts

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

## Builds on (most cited first, 30 of 35)

- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Deep metric learning using Triplet network](https://mlsanity.com/paper/1412.6622/) (2014)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Fast Matrix Factorization for Online Recommendation with Implicit Feedback](https://mlsanity.com/paper/1708.05024/) (2017)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Beyond Locality-Sensitive Hashing](https://mlsanity.com/paper/1306.1547/) (2013)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [Speeding Up Sparsification using Inner Product Search Data Structures](https://mlsanity.com/paper/2204.03209/) (2022)
- [Visual Search at Pinterest](https://mlsanity.com/paper/1505.07647/) (2015)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and More](https://mlsanity.com/paper/2103.10891/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search](https://mlsanity.com/paper/1904.02033/) (2019)
- [Shop The Look: Building a Large Scale Visual Shopping System at Pinterest](https://mlsanity.com/paper/2006.10866/) (2020)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures](https://mlsanity.com/paper/2207.09002/) (2022)
- [Edge-Weighted Online Bipartite Matching](https://mlsanity.com/paper/2005.01929/) (2020)
- [Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program](https://mlsanity.com/paper/2103.13024/) (2021)
- [Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model](https://mlsanity.com/paper/1810.07903/) (2018)
- [How to Match when All Vertices Arrive Online](https://mlsanity.com/paper/1802.03905/) (2018)
- [Approximate Nearest Neighbors in Limited Space](https://mlsanity.com/paper/1807.00112/) (2018)
- [Online Matching with General Arrivals](https://mlsanity.com/paper/1904.08255/) (2019)

## Built on by (most cited first, 7 of 7)

- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [On Computational Limits of FlowAR Models: Expressivity and Efficiency](https://mlsanity.com/paper/2502.16490/) (2025)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Fast and Efficient Matching Algorithm with Deadline Instances](https://mlsanity.com/paper/2305.08353/) (2023)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [HOFAR: High-Order Augmentation of Flow Autoregressive Transformers](https://mlsanity.com/paper/2503.08032/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)

## 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.