Abstract:Given $N$ real numbers whose sum is an integer, we study the problem of finding $N$ integers that preserve the sum while minimizing the rounding error. We first show that every optimal solution necessarily rounds each coordinate either to its floor or its ceiling, reducing the problem to the selection of the coordinates to be rounded upward. This characterization extends to a class of separable convex integer optimization problems with a single sum constraint.
For the resulting optimization problem we characterize the complete set of optimal solutions and show that rounding upward the largest fractional parts simultaneously minimizes every $L^q$ rounding error, $1\le q\le\infty$. More generally, the resulting error vector is minimal in the weak-majorization order and therefore minimizes every symmetric convex loss of the rounding errors. When the $L^q$-optimal solution is not unique, we provide an explicit tie-breaking rule that minimizes the relative rounding error among all optimal solutions.
These structural results lead to a deterministic algorithm with linear $O(N)$ worst-case complexity. Unlike independent randomized rounding, which preserves the target coordinates and the sum constraint only in expectation, the proposed method computes an exactly feasible, provably optimal integer rounding with deterministic optimality guarantee. Besides solving the constrained rounding problem, the algorithm applies as the rounding step in relaxed integer optimization problems with a single conservation constraint.
From: Rama Cont [view email]
[v1]
Tue, 30 Dec 2014 21:01:08 UTC (12 KB)
[v2]
Tue, 4 Aug 2026 17:32:07 UTC (22 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。