Optimal Roundings of Sequences and Matrices
Optimal Roundings of Sequences and Matrices
复制标题
序列和矩阵的最佳舍入
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
T. Tokuyama
中科院分区：
文献类型：
--
作者：
T. Asano;Tomomi Matsui;T. Tokuyama
在本文中，我们讨论将一个实数列（相应地，矩阵）最优舍入为一个整数列（相应地，矩阵）的问题。我们的最优性标准是最小化输入数列（相应地，矩阵）\(A\)和输出\(B\)之间的加权\(l_{\infty}\)距离\(Dist_{\infty}^{F, w}(A, B)\)。该距离取决于用于数列舍入（相应地，矩阵舍入）的区间族（相应地，矩形区域族）\(F\)以及该族上的正值权重函数\(w\)。对于任何权重函数\(w\)和任何区间族\(F\)，我们针对加权\(l_{\infty}\)距离的数列舍入问题给出了有效的多项式时间算法。对于矩阵舍入问题，我们证明，对于与所有\(2\times2\)正方形区域的族\(W_2\)相关联的未加权\(l_{\infty}\)距离，计算近似比小于\(2\)的近似解是\(NP\)难的。
In this paper, we discuss the problem of computing an optimal rounding of a real sequence (resp. matrix) into an integral sequence (resp. matrix). Our criterion of the optimality is to minimize the weighted l∞-distance Dist∞F, w (A, B) between an input sequence (resp. matrix) A and the output B. The distance is dependent on a family F of intervals (resp. rectangular regions) for the sequence rounding (resp. matrix rounding) and positive-valued weight function w on the family. We give efficient polynomial-time algorithms for the sequence-rounding problem for weighted l∞-distance with respect to any weight function w and any family F of intervals. For the matrix-rounding problem, we prove that it is NP-hard to compute an approximate solution with approximation ratio smaller than 2 with respect to the unweighted l∞-distance associated with the family W2 of all 2 × 2 square regions.