Feb 21, 2017, 4pm
PDL C-401
Rebecca Hoberg, Department of Mathematics, University of Washington

Abstract: The number balancing problem (NBP) is the following: given real numbers $a_1,…,a_n \in [0,1]$, find two distinct subsets of $[n]$ so that the difference of the sums is minimized. An application of the pigeonhole principle shows that there is always a solution where the difference is at most $O(\frac{\sqrt{n}}{2^n})$. Finding the minimum, however, is NP-hard. In polynomial time, the differencing algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most $n^{-\Theta(\log n)}$, but no further improvement has been made since then.

In this talk, we show that an approximate oracle for Minkowski’s Theorem gives an approximate NBP oracle, and conversely an approximate NBP oracle gives an approximate Minkowski oracle. In particular, we prove that any polynomial time algorithm that guarantees a NBP solution of difference at most $O(\frac{2^\sqrt{n}}{2^n})$ would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem. This is joint work with Harish Ramadas, Thomas Rothvoss, and Xin Yang.