  Given real numbers whose sum is an integer, we study the problem of finding
integers which match these real numbers as closely as possible, in the sense of
L^p norm, while preserving the sum. We describe the structure of solutions for
this integer optimization problem and propose an algorithm with complexity O(N
log N) for solving it. In contrast to fractional rounding and randomized
rounding, which yield biased estimators of the solution when applied to this
problem, our method yields an exact solution which minimizes the relative
rounding error across the set of all solutions for any value of p greater than
1, while avoiding the complexity of exhaustive search. The proposed algorithm
also solves a class of integer optimization problems with integer constraints
and may be used as the rounding step of relaxed integer programming problems,
for rounding real-valued solutions. We give several examples of applications
for the proposed algorithm.
