Fast and Efficient Matching Algorithm with Deadline Instances

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 $\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}$ (the longest time a node can be matched) into account. In this paper, we introduce a market model with $\mathrm{d}\mathrm{e}\mathrm{a}\mathrm{d}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{e}$ first. Next, we present our two optimized algorithms ($\text{textsc}FastGreedy$ and $\text{textsc}FastPostponedGreedy$) and offer theoretical proof of the time complexity and correctness of our algorithms. In $\text{textsc}FastGreedy$ algorithm, we have already known if a node is a buyer or a seller. But in $\text{textsc}FastPostponedGreedy$ 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 $\epsilon \in (0,0.1)$ denote the relative error of the real weight of each edge. The competitive ratio of original $\text{textsc}Greedy$ and $\text{textsc}PostponedGreedy$ is $\frac{1}{2}$ and $\frac{1}{4}$ respectively. Based on these two original algorithms, we proposed $\text{textsc}FastGreedy$ and $\text{textsc}FastPostponedGreedy$ algorithms and the competitive ratio of them is $\frac{1-\epsilon }{2}$ and $\frac{1-\epsilon }{4}$ respectively. At the same time, our algorithms run faster than the original two algorithms. Given $n$ nodes in ${\mathbb{R}}^d$, we decrease the time complexity from $O(nd)$ to $\tilde{O}({\epsilon }^{-2}\cdot (n+d))$, where for any function $f$, we use $\tilde{O}(f)$ to denote $f\cdot \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log f)$.