## Abstract

The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in [1; 1]n, find a signing (a) 2 f1g of each vector a to minimize the discrepancy k P a (a) ak1. This problem has been extensively studied in the static/ofiine setting. In this paper we initiate its study in the fully-dynamic setting with recourse: the algorithm sees a stream of T insertions and deletions of vectors, and at each time must maintain a low-discrepancy signing, while also minimizing the amortized recourse (the number of times any vector changes its sign) per update. For general vectors, we show algorithms which almost match Spencer's O( p n) offine discrepancy bound, with O(n polylog T) amortized recourse per update. The crucial idea behind our algorithm is to compute a basic feasible solution to the linear relaxation in a distributed and recursive manner, which helps find a low-discrepancy signing. We bound the recourse using the distributed computation of the basic solution, and argue that only a small part of the instance needs to be re-computed at each update. Since vector balancing has also been greatly studied for sparse vectors, we then give algorithms for low- discrepancy edge orientation, where we dynamically maintain signings for 2-sparse vectors in an n-dimensional space. Alternatively, this can be seen as orienting a dynamic set of edges of an n-vertex graph to minimize the discrepancy, i.e., the absolute difference between in- and out-degrees at any vertex. We present a deterministic algorithm with O(polylog n) discrepancy and O(polylog n) amortized recourse. The core ideas are to dynamically maintain an expander-decomposition with low recourse (using a very simple approach), and then to show that, as the expanders change over time, a natural local-search algorithm converges quickly (i.e., with low recourse) to a low-discrepancy solution. We also give strong lower bounds (with some matching upper bounds) for local-search discrepancy minimization algorithms for vector balancing and edge orientation.

Original language | English (US) |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |

Publisher | Association for Computing Machinery |

Pages | 1356-1383 |

Number of pages | 28 |

ISBN (Electronic) | 9781611977073 |

State | Published - 2022 |

Event | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States Duration: Jan 9 2022 → Jan 12 2022 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2022-January |

### Conference

Conference | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |
---|---|

Country/Territory | United States |

City | Alexander |

Period | 1/9/22 → 1/12/22 |

## ASJC Scopus subject areas

- Software
- General Mathematics