2021/02/04 by Arbour, David, Dimmery, Drew, Mai, Tung +1
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2102.02765
We study the online discrepancy minimization problem for vectors in ℝd in the oblivious setting where an adversary is allowed fix the vectors x1, x2, …, xn in arbitrary order ahead of time. We give an algorithm that maintains O(√(log(nd/δ))) discrepancy with probability 1-δ, matching the lower bound given in [Bansal et al. 2020] up to an O(√(log log n)) factor in the high-probability regime. We also provide results for the weighted and multi-color versions of the problem.