{'fraction_non_alphanumeric': 0.01556420233463035, 'fraction_numerical': 0.007782101167315175, 'mean_word_length': 4.988372093023256, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Weighted Matching

Abstract We introduce and study online versions of weighted matching problems in metric spaces. We present a simple 2 k − 1 competitive algorithm for online minimum weighted bipartite matching where 2 k is the number of nodes. We show that this competitiveness is optimal. For online maximum matching, we prove that the greedy algorithm achieves an optimal competitive factor of 3. In contrast, we prove that the greedy algorithm performs exponentially poorly for online minimum matching.