Two-way rounding
| dc.creator | Knuth, Donald E. | |
| dc.date | 1995-04-01 | |
| dc.date.accessioned | 2026-07-07T09:15:19Z | |
| dc.date.available | 2026-07-07T09:15:19Z | |
| dc.description | Given $n$ real numbers $0\leq x_1,...,x_n<1$ and a permutation~$σ$ of $\{1,...,n\}$, we can always find $\xbar_1,...,\xbar_n\in\{0,1\}$ so that the partial sums $\xbar_1+... +\xbar_k$ and $\xbar_{σ1}+... +\xbar_{σk}$ differ from the unrounded values $x_1+... + x_k$ and $x_{σ1}+... +x_{σk}$ by at most $n/(n+1)$, for $1\leq k\leq n$. The latter bound is best possible. The proof uses an elementary argument about flows in a certain network, and leads to a simple algorithm that finds an optimum way to round. | |
| dc.identifier | https://arxiv.org/abs/math/9504228 | |
| dc.identifier | http://arxiv.org/abs/math/9504228 | |
| dc.identifier | SIAM J. Discrete Math. 8 (1995), no. 2, 281--290 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/152979 | |
| dc.subject | Optimization and Control | |
| dc.title | Two-way rounding | |
| dc.type | text |