...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Rounding in symmetric matrices and undirected graphs
【24h】

Rounding in symmetric matrices and undirected graphs

机译：在对称矩阵和无向图中四舍五入

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider the problem of rounding the entries of a matrix without distorting the row, column, and grand totals. This problem arises in controlling statistical disclosure, in data analysis, and elsewhere. There are algorithms in the literature which produce roundings that are "tight" in the sense of distorting the totals very little. We concentrate on the case of symmetric matrices. The existing algorithms do not preserve symmetry. In fact, the best symmetric rounding of a symmetric matrix may not be as tight as its best unsymmetric rounding. We suggest three different relaxations of the tightness contraints, which admit symmetric solutions. In each case we find the strongest possible result concerning the existence of a rounding of prescribed tightness. We also give efficient algorithms to determine if roundings with specified distortion bounds exist and, if so, construct such a rounding. These results and algorithms are based on a graph-theoretic model of the situation in which we are given an edge-weighted undirected graph and we wish to round the edge weights so that the weight sums at any vertex, and the total weight sum over all edges, are changed as little as possible. We use graph factors as our main tool. As a consequence of our work on symmetric matrices we also provide more efficient algorithms for roundings in general matrices.
机译：我们考虑在不扭曲行，列和总计的情况下舍入矩阵项的问题。在控制统计信息公开，数据分析和其他方面会出现此问题。文献中有一些算法会产生舍入不紧密的舍入，就总的失真而言，它很小。我们专注于对称矩阵的情况。现有算法不能保持对称性。实际上，对称矩阵的最佳对称舍入可能不如其最佳非对称舍入那么紧密。我们建议松紧约束的三种不同松弛方式，它们允许使用对称解。在每种情况下，我们都发现与规定的紧密度舍入有关的最强结果。我们还提供了有效的算法来确定是否存在具有指定失真范围的舍入，如果存在，则构造这样的舍入。这些结果和算法基于以下情况的图论模型：给定一个边缘加权无向图，并且希望对边缘权重取整，以使权重在任何顶点求和，而总权重在所有顶点求和边缘，尽可能少地改变。我们使用图形因子作为主要工具。作为我们在对称矩阵上的工作的结果，我们还为通用矩阵的舍入提供了更有效的算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号