Generating dual-bounded hypergraphs
Generating dual-bounded hypergraphs
复制标题
生成双界超图
DOI：
10.1080/1055678021000060801
复制
发表时间：
2002
影响因子：
2.2
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
E. Boros;Khaled M. Elbassioni;V. Gurvich;L. Khachiyan
本文综述了隐给定超图的生成及其在布尔和整数规划、数据挖掘、可靠性理论和组合数学中的应用。给定有限集合V的子集上的单调性质~，当~由多项式时间可满足预言机给出时，考虑递增生成满足性质~的极小子集族F π的问题.对于一些有趣的单调性质，族F π原来是一致对偶有界的，允许递增有效枚举F π的成员。重要的应用包括数据库的最小不频繁集的有效生成（数据挖掘），最小连通性确保从给定列表中收集子图（可靠性理论），整数变量单调不等式系统的最小可行解（整数规划），给定列表中的子空间的最小生成集合（线性代数）和最大独立集的交集拟阵（组合优化）。与这些结果相反，生成所有不具有性质~的极大子集族的类似问题对于上述几乎所有应用都是NP-困难的。
This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and maximal independent sets in the intersection of matroids (combinatorial optimization). In contrast to these results, the analogous problem of generating the family of all maximal subsets not having property ~ is NP-hard for almost all applications mentioned above.
单调对偶化及相关主题
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
112.Yuta Halvorson;Naoki Hasimoto;Kazuhisa Makino
通讯作者：
Kazuhisa Makino
DOI：
--
发表时间：
2008
期刊：
Discrete Optimization 5, No.1
影响因子：
--
作者：
A.Takemura;Ruriko Yoshida.
通讯作者：
Ruriko Yoshida.