English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The number balancing (NBP) problem is the following: given real numbers$a_1,\ldots,a_n \in [0,1]$, find two disjoint subsets $I_1,I_2 \subseteq [n]$so that the difference $|\sum_{i \in I_1}a_i - \sum_{i \in I_2}a_i|$ of theirsums is minimized. An application of the pigeonhole principle shows that thereis 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 differencingalgorithm by Karmarkar and Karp from 1982 can produce a solution withdifference at most $n^{-\Theta(\log n)}$, but no further improvement has beenmade since then.  In this paper, we show a relationship between NBP and Minkowski's Theorem.First we show that an approximate oracle for Minkowski's Theorem gives anapproximate NBP oracle. Perhaps more surprisingly, we show that an approximateNBP oracle gives an approximate Minkowski oracle. In particular, we prove thatany polynomial time algorithm that guarantees a solution of difference at most$2^{\sqrt{n}} / 2^{n}$ would give a polynomial approximation for Minkowski aswell as a polynomial factor approximation algorithm for the Shortest VectorProblem.

Number Balancing is as hard as Minkowski's Theorem and Shortest Vector