We consider the (offline) vertex-weighted Online Matching problem under Known Identical and Independent Distributions (KIID) with integral arrival rates. We propose a meta-algorithm, denoted as RTB, featuring Real-Time Boosting, where the core idea is as follows. Consider a bipartite graph G= (I, J, E), where I and J represent the sets of offline and online nodes, respectively. Let x= (x₈₉) 0, 1^|E|, where x₈₉ for (i, j) E represents the probability that edge (i, j) is matched in an offline optimal policy (a. k. a. a clairvoyant optimal policy), typically obtained by solving a benchmark linear program (LP). Upon the arrival of an online node j at some time t 0, 1, RTB samples a safe (available) neighbor i I₉, ₓ with probability x₈₉/₈' ₈_₉, ₓ x₈'₉ and matches it to j, where I₉, ₓ denotes the set of safe offline neighbors of j. In this paper, we showcase the power of Real-Time Boosting by demonstrating that RTB, when fed with X^*, achieves a competitive ratio of (2e⁴ - 8e² + 21e - 27) / (2e⁴) 0. 7341, where X^* \0, 1/3, 2/3\^|E| is a random vector obtained by applying a customized dependent rounding technique due to Brubach et al. (Algorithmica, 2020). Our result improves upon the state-of-the-art ratios of 0. 7299 by Brubach et al. (Algorithmica, 2020) and 0. 725 by Jaillet and Lu (Mathematics of Operations Research, 2013). Notably, this improvement does not stem from the algorithm itself but from a new competitive analysis methodology: We introduce an Ordinary Differential Equation (ODE) system-based approach that enables a holistic analysis of RTB. We anticipate that utilizing other well-structured vectors from more advanced rounding techniques could potentially yield further improvements in the competitiveness.
Pan Xu (Wed,) studied this question.