Dynamic online matching with budget refills - ENSAE Paris Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2024

Dynamic online matching with budget refills

Résumé

Inspired by sequential budgeted allocation problems, we study the online matching problem with budget refills. In this context, we consider an online bipartite graph G=(U,V,E), where the nodes in $V$ are discovered sequentially and nodes in $U$ are known beforehand. Each $u\in U$ is endowed with a budget $b_{u,t}\in \lN$ that dynamically evolves over time. Unlike the canonical setting, in many applications, the budget can be refilled from time to time, which leads to a much richer dynamic that we consider here. Intuitively, adding extra budgets in $U$ seems to ease the matching task, and our results support this intuition. In fact, for the stochastic framework considered where we studied the matching size built by $\greedy$ algorithm on an Erdős-Réyni random graph, we showed that the matching size generated by $\greedy$ converges with high probability to a solution of an explicit system of ODE. Moreover, under specific conditions, the competitive ratio (performance measure of the algorithm) can even tend to 1. For the adversarial part, where the graph considered is deterministic and the algorithm used is $\balance$, the $b$-matching bound holds when the refills are scarce. However, when refills are regular, our results suggest a potential improvement in algorithm performance. In both cases, $\balance$ algorithm manages to reach the performance of the upper bound on the adversarial graphs considered.
Fichier principal
Vignette du fichier
OR_submission_matching_with_refills.pdf (531.53 Ko) Télécharger le fichier
main_alt.pdf (481.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04573598 , version 1 (15-05-2024)

Identifiants

  • HAL Id : hal-04573598 , version 1

Citer

Maria Cherifa, Clément Calauzènes, Vianney Perchet. Dynamic online matching with budget refills. 2024. ⟨hal-04573598⟩
0 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More