Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
share
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] ⊆ [0,1] is nearly-balanced. We define 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 O(√(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.<cit.> for the online envy minimization problem when the arrivals are stochastic.
READ FULL TEXT