Online carpooling edge assignments achieve cube root discrepancy bounds
The Cube-Root Phenomenon in Online Carpooling
Data Structures and Algorithms
Summary
In online carpooling, each new ride request (edge) must be quickly assigned a direction between two people (vertices) to keep the balance of rides fair. The authors study how well the simple greedy method can keep this balance and prove it is nearly as good as any method can be, improving previous results. They also show that in random cases, the balance can be kept even tighter than expected, revealing a new pattern in how errors grow with more rides. Their work refines mathematical tools to better understand these online balancing problems.
What this means in practice
- •For network schedulers: Design online edge-orientation methods that minimize load imbalance in dynamic communication graphs with arrival uncertainty.
- •For data center traffic managers: Use improved discrepancy bounds to balance communication requests dynamically and reduce bottlenecks under random task assignments.
A theory result. No direct application yet.
Authors
Nikhil Bansal, Milind Prabhu, Sahil Singla, Siddharth M. Sundaram
Abstract
We consider the online carpooling problem, where edges arrive online and must be oriented immediately while keeping the discrepancy between the indegree and outdegree at each vertex small. We prove that the natural Greedy algorithm incurs discrepancy $O(\min\{T^{1/3},n\})$ after $T$ arrivals. This resolves a question of Ajtai et al., who showed that any deterministic algorithm must incur $Ω(\min\{T^{1/3},n\})$ discrepancy, and gave an algorithm with $O(\min\{T^{1/2},n\})$ discrepancy. We also show a similar square-root to cube-root improvement in the stochastic setting, where $O(n)$ edges are sampled independently from an underlying $n$-vertex graph $G$. Formally, we show an $O((\log n)^{1/3})$ bound for random arrivals from any $Δ$-regular graph $G$. When $Δ= Ω((\log n)^3)$, we show the more refined bound of $O((\log n/\log Δ)^{1/3}+\log\log n)$ on the discrepancy. We show that the cube-root term in the previous bound is essential, while the $\log\log n$ term is already known to be necessary for random arrivals from complete graphs. The previous upper bounds here were $O((\log n)^{1/2})$, which follow from the breakthrough works on online discrepancy due to Kulkarni, Reis, and Rothvoss, and Aden-Ali. Our techniques for proving such cube-root-type bounds may be of independent interest, as the standard quadratic-potential and subgaussian analyses underlying the previous general bounds appear inherently unable to go below square-root-type guarantees.