The ACO Seminar (2021–2022)

The balancing of items -- or discrepany -- arises naturally in Computer Science and Discrete Mathematics. Here we consider n vectors in n-space, all coordinate +1 or -1. We create a signed sum of the vectors, with the goal that this signed sum be as small as possible, Here we use the max [or L-infinity] norm, though many variants are possible. We create a game with Paul (Erdos) selecting the vectors and Carole (find the anagram!) choosing to add or subtract. This becomes four (two TIMES two) different problems. The vectors (Paul) can be chosen randomly or adversarially, equivalently average case and worst case analysis for Carole. The choice of signed sum (Carole) can be done on-line or off-line. All four variants are interesting and are at least partially solved. We emphasize the random (Paul) on-line (Carole) case, joint work with Nikhil Bansal