A Simple Algorithm for Dynamic Carpooling with Recourse
Efron et al. — 2025
Résumé (FR)
Cet article aborde le problème du covoiturage entièrement dynamique avec recours, où des arêtes arrivent et partent en ligne depuis un graphe selon un adversaire adaptatif. L’objectif est de maintenir une orientation qui minimise la discordance, c’est-à-dire la différence maximale entre le degré entrant et sortant en tout noeud. L’algorithme proposé, basé sur des cycles, simplifie et améliore les résultats antérieurs de Gupta et al. (SODA’22). Ce travail fournit des garanties théoriques rigoureuses pour le problème d’orientation de graphe dynamique qui sous-tend les algorithmes de covoiturage. Il constitue une contribution fondamentale à la compréhension algorithmique du covoiturage dynamique.
Summary (EN)
This paper addresses the fully-dynamic carpooling problem with recourse, where edges arrive and depart online from a graph according to an adaptive adversary, with the goal of maintaining an orientation that keeps discrepancy minimal. A simple algorithm based on cycles is presented that simplifies and improves prior work by Gupta et al. from SODA’22, providing rigorous theoretical guarantees for dynamic graph orientation underlying carpooling algorithms.
Points clés
| Aspect | Détail |
|---|