cs.DS cs.CG cs.DM cs.GT
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization. Consider a unit interval 0,1 in which n points arrive one by one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably color it in 1, 1 while ensuring that every interval a,b subseteq 0,1 is nearly balanced. We define emph discrepancy as the largest imbalance of any interval during the entire process. If all the arriving points were known upfront then we can color them alternately to achieve a discrepancy of 1 . What is the minimum possible expected discrepancy when we color the points online? We show that the discrepancy of the above problem is sub polynomial in n and that no algorithm can achieve a constant discrepancy. This is a substantial improvement over the trivial random coloring that only gets an widetilde O ( sqrt n) discrepancy. We then obtain similar results for a natural generalization of this problem to 2 dimensions where the points arrive uniformly at random in a unit square. This generalization allows us to improve recent results of Benade et al. cite BenadeKPP EC18 for the online envy minimization problem when the arrivals are stochastic.