2021/07/02 by Nathan Noiry, Flore Sentenac, Noiry, Nathan +3 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems #Machine Learning (stat.ML) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2107.00995
openalex publication_date 2021/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by sequential budgeted allocation problems, we investigate online\nmatching problems where connections between vertices are not i.i.d., but they\nhave fixed degree distributions -- the so-called configuration model. We\nestimate the competitive ratio of the simplest algorithm, GREEDY, by\napproximating some relevant stochastic discrete processes by their continuous\ncounterparts, that are solutions of an explicit system of partial differential\nequations. This technique gives precise bounds on the estimation errors, with\narbitrarily high probability as the problem size increases. In particular, it\nallows the formal comparison between different configuration models. We also\nprove that, quite surprisingly, GREEDY can have better performance guarantees\nthan RANKING, another celebrated algorithm for online matching that usually\noutperforms the former.\n