...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Dual-bounded generating problems: weighted transversals of a hypergraph
【24h】

Dual-bounded generating problems: weighted transversals of a hypergraph

机译：双界生成问题：超图的加权横切

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

摘要

We consider a generalization of the notion of transversal to a finite hypergraph, the so-called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of an input hypergraph A and a non-negative threshold vector, we define a weighted transversal as a minimal vertex set which intersects all the hyperedges of A except for a sub-family of total weight not exceeding the given threshold vector. Weighted transversals generalize partial and multiple transversals introduced in Boros et al. (SIAM J. Comput. 30 (6) (2001)) and also include minimal binary solutions to non-negative systems of linear inequalities and minimal weighted infrequent sets in databases. We show that the hypergraph of all weighted transversals is dual-bounded, i.e., the size of its transversal hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. For instance, we show that for any row-weighted m×n binary matrix and any threshold weight t, the number of maximal sets of columns whose row support has weight above t is at most m times the number of minimal sets of columns with row support of total weight below t. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal weighted infrequent sets of columns for a given binary matrix.
机译：我们考虑将横向概念推广到有限超图，即所谓的加权横向。给定分配给输入超图A的每个超边的非负权重向量和非负阈值向量，我们将加权横向定义为与A的所有超边相交的最小顶点集，该子集除总权重的子族外不超过给定的阈值向量。加权横断面概括了Boros等人介绍的部分和多次横断面。 （SIAM J. Comput。30（6）（2001）），并且还包括线性不等式的非负系统的最小二元解和数据库中的最小加权不频繁集。我们显示所有加权横向的超图是双界的，即其横向超图的大小是加权横向数和输入超图的大小的多项式。我们的界限基于极值集理论和阈值布尔逻辑的新不等式，这些不等式可能具有独立的意义。例如，我们表明对于任何行加权的m×n二元矩阵和任何阈值权重t，行支持权重大于t的最大列集的数量最多是具有行的列最小集的数量的m倍。总重量低于t的支撑。我们还证明了生成给定超图的所有加权横截面的问题是多项式时间可归结为另一个超图的所有普通横截面的生成，即众所周知的超图对偶化问题。作为推论，我们获得了一个增量准多项式时间算法，用于生成给定超图的所有加权横向。作为特殊情况，此结果包括为给定的非负线性不等式系统生成所有最小布尔解，以及为给定二进制矩阵生成所有最小加权不频繁列集。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号