In this paper we study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an Lp-discrepancy measure between them. To define the Lp-discrepancy measure, we introduce a family F of regions (rigid submatrices) of the matrix, and consider a hypergraph defined by the family. The difficulty of the problem depends on the choice of the region family F. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions, and give some nontrivial upper bounds for the Lp-discrepancy. Then, we propose "laminar family" for constructing a practical and well-solvable class of F. Indeed, we show that the problem is solvable in polynomial time if F is a union of two laminar families. Finally, we show that the matrix rounding using L1-discrepancy for a union of two laminar families is suitable for developing a high-quality digital-halftoning software.
展开▼
机译：在本文中，我们研究了将实值矩阵舍入为整数值矩阵以最小化它们之间的 L p 差异度量的问题。为了定义 L p 差异度量，我们引入矩阵区域（刚性子矩阵）的族 F ，并考虑定义的超图由家人。问题的难度取决于区域族 F的选择。首先，我们使用带有凸分段线性目标函数的整数规划问题来研究舍入问题，并为< I> L p -差异。然后，我们提出了“层状族”来构造一个实用且易于解决的 F类。实际上，我们证明了如果 F 是一个整数，则该问题可以在多项式时间内解决。两个层状家庭的联合。最后，我们证明了使用 L 1 偏差对两个层流族的并集进行矩阵舍入适合于开发高质量的数字半音调软件。
展开▼
