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