# Fast and Efficient Matching Algorithm with Deadline Instances

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 51 references that are in the map.
- First posted on arXiv 15 May 2023.

## Builds on (most cited first, 29 of 29)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path](https://mlsanity.com/paper/2011.05365/) (2020)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [Speeding Up Sparsification using Inner Product Search Data Structures](https://mlsanity.com/paper/2204.03209/) (2022)
- [Training Overparametrized Neural Networks in Sublinear Time](https://mlsanity.com/paper/2208.04508/) (2022)
- [Discrepancy Minimization in Input-Sparsity Time](https://mlsanity.com/paper/2210.12468/) (2022)
- [A General Algorithm for Solving Rank-one Matrix Sensing](https://mlsanity.com/paper/2303.12298/) (2023)
- [Convex Minimization with Integer Minima in widetilde O(n4) Time](https://mlsanity.com/paper/2304.03426/) (2023)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Maximum Weight Online Matching with Deadlines](https://mlsanity.com/paper/1808.03526/) (2018)
- [Beating Greedy for Stochastic Bipartite Matching](https://mlsanity.com/paper/1909.12760/) (2019)
- [What do Asian Religions Have in Common? An Unsupervised Text Analytics Exploration](https://mlsanity.com/paper/1912.10847/) (2019)
- [Greedy Online Bipartite Matching on Random Graphs](https://mlsanity.com/paper/1307.2536/) (2013)
- [Online Bipartite Matching with Decomposable Weights](https://mlsanity.com/paper/1409.2139/) (2014)
- [Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals](https://mlsanity.com/paper/1804.07458/) (2018)
- [Randomized Two-Valued Bounded Delay Online Buffer Management](https://mlsanity.com/paper/2004.14715/) (2020)

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

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [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)
- [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)

The online weighted matching problem is a fundamental problem in machine learning due to its numerous applications. Despite many efforts in this area, existing algorithms are either too slow or don't take deadline (the longest time a node can be matched) into account. In this paper, we introduce a market model with deadline first. Next, we present our two optimized algorithms (textscFastGreedy and textscFastPostponedGreedy) and offer theoretical proof of the time complexity and correctness of our algorithms. In textscFastGreedy algorithm, we have already known if a node is a buyer or a seller. But in textscFastPostponedGreedy algorithm, the status of each node is unknown at first. Then, we generalize a sketching matrix to run the original and our algorithms on both real data sets and synthetic data sets. Let ε ∈ (0,0.1) denote the relative error of the real weight of each edge. The competitive ratio of original textscGreedy and textscPostponedGreedy is frac12 and frac14 respectively. Based on these two original algorithms, we proposed textscFastGreedy and textscFastPostponedGreedy algorithms and the competitive ratio of them is frac1 - ε2 and frac1 - ε4 respectively. At the same time, our algorithms run faster than the original two algorithms. Given n nodes in ℝ ^ d, we decrease the time complexity from O(nd) to widetildeO(ε-2 · (n + d)), where for any function f, we use widetildeO(f) to denote f · poly(log f).