Online carpooling against an oblivious adversaryResearch Paper
In the online carpooling problem (Fagin–Williams 1983), people share rides in pairs and each ride must immediately name one of the two as the driver; the goal is that nobody drives much more or much less than their fair share. In graph language, edges on vertices arrive one at a time and must be oriented immediately, keeping the indegree minus outdegree…