On‐line balancing of random inputs. Issue 4 (25th August 2020)

• Record Type: Journal Article
• Authors: Bansal, Nikhil; Spencer, Joel H.
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 879
• Page End: 891
• Publication Date: 2020-08-25
• Subjects: discrepancy -- online algorithms -- random vectors; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20955
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We consider an online vector balancing game where vectors v t, chosen uniformly at random in {− 1, + 1} n, arrive over time and a sign x t ∈ {− 1, + 1} must be picked immediately upon the arrival of v t . The goal is to minimize the L ∞ norm of the signed sum ∑ t x t v t . We give an online strategy for picking the signs x t that has value O ( n 1/2 ) with high probability. Up to constants, this is the best possible even when the vectors are given in advance.