A Simple Algorithm for Dynamic Carpooling with Recourse

2024/11/12 by Efron, Yuval, Patel, Shyamal, Stein, Cliff · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2411.07553

Abstract

We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph G with n nodes according to an adaptive adversary. Our goal is to maintain an orientation H of G that keeps the discrepancy, defined as max_{v ∈ V} |deg_H⁺(v) - deg_H^-(v)|, small at all times. We present a simple algorithm and analysis for this problem with recourse based on cycles that simplifies and improves on a result of Gupta et al. [SODA '22].

Cited by

• Weighted Chairman Assignment and Flow-Time Scheduling

Related

• Online Carpooling using Expander Decompositions
• Approximation Algorithms for the Maximum Carpool Matching Problem
• Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
• Optimally reconnecting weighted graphs against an edge-destroying adversary
• Ride Sharing with a Vehicle of Unlimited Capacity