Online carpooling using expander decompositions

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the online carpooling problem: given n vertices, a sequence of edges arrive over time. When an edge et = (ut, vt) arrives at time step t, the algorithm must orient the edge either as vt → ut or ut → vt, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog(n, T ) maximum discrepancy (w.h.p) over any sequence of T arrivals, when the arriving edges are sampled independently and uniformly from any given graph G. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were O(√n log n)discrepancy for any adversarial sequence of arrivals, or O(loglog n)-discrepancy bounds for the stochastic arrivals when G is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when G is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.

Original languageEnglish (US)
Title of host publication40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020
EditorsNitin Saxena, Sunil Simon
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771740
DOIs
StatePublished - Dec 2020
Event40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020 - Virtual, Goa, India
Duration: Dec 14 2020Dec 18 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume182
ISSN (Print)1868-8969

Conference

Conference40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020
Country/TerritoryIndia
CityVirtual, Goa
Period12/14/2012/18/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Carpooling
  • Discrepancy Minimization
  • Online Algorithms

Fingerprint

Dive into the research topics of 'Online carpooling using expander decompositions'. Together they form a unique fingerprint.

Cite this