On‐line balancing of random inputs
On‐line balancing of random inputs
复制标题
随机输入的在线平衡
DOI：
10.1002/rsa.20955
复制
发表时间：
2019
影响因子：
1
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
N. Bansal;J. Spencer
我们考虑一个在线向量平衡游戏，其中向量vt，在{−1，+ 1}n中随机均匀选择，随着时间的推移到达，并且符号xt∈{−1，+ 1}必须在vt到达时立即被选中。目标是最小化有符号和∑txtvt的L∞范数。我们给出了一种在线策略来选择具有高概率值为O（n1/2）的符号xt。在常量范围内，这是最好的，即使向量是预先给定的。
We consider an online vector balancing game where vectors vt, chosen uniformly at random in {− 1, + 1}n, arrive over time and a sign xt ∈ {− 1, + 1} must be picked immediately upon the arrival of vt. The goal is to minimize the L∞ norm of the signed sum ∑txtvt . We give an online strategy for picking the signs xt that has value O(n1/2) with high probability. Up to constants, this is the best possible even when the vectors are given in advance.
DOI：
10.1088/1751-8121/ab227a
发表时间：
2019-07-19
影响因子：
2.1
作者：
Aubin, Benjamin;Perkins, Will;Zdeborova, Lenka
通讯作者：
Zdeborova, Lenka