Online Discrepancy with Recourse for Vectors and Graphs

arXiv2111.06308MaRDI QIDQ6382802FDOQ6382802

Authors: Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, Sahil Singla 

Publication date: 11 November 2021

Abstract: The vector-balancing problem is a fundamental problem in discrepancy theory: given T vectors in $[-1,1{]}^n$, find a signing $sigma(a)inpm1$ of each vector $a$ to minimize the discrepancy $|su{m}_{a}sigma(a)cdota{|}_{infty}$. This problem has been extensively studied in the static/offline 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(sqrtn)$ offline discrepancy bound, with $O(ncdotpoly!logT)$ amortized recourse per update. The crucial idea is to compute a basic feasible solution to the linear relaxation in a distributed and recursive manner, which helps find a low-discrepancy signing. To bound recourse we 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. Alternatively, this can be seen as orienting a dynamic set of edges of an n-vertex graph to minimize the absolute difference between in- and out-degrees at any vertex. We present a deterministic algorithm with $O(poly!logn)$ discrepancy and $O(poly!logn)$ amortized recourse. The core ideas are to dynamically maintain an expander-decomposition with low recourse 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 for local-search discrepancy minimization algorithms.

This page was built for publication: Online Discrepancy with Recourse for Vectors and Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382802)