2019/10/02 by Haotian Jiang, Jiang, Haotian, Janardhan Kulkarni +3
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.1910.01073
openalex publication_date 2019/10/02 · openalex created_date 2019/10/10 · openalex updated_date 2026/07/28
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 \widetildeO(√ 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.\citeBenadeKPP-EC18 for the online envy minimization problem when the arrivals are stochastic.