Polynomial time algorithm for dualizing a monotone DNF

对偶单调 DNF 的多项式时间算法

• 批准号: 10680365
• 负责人: TAMAKI Hisao
• 金额: $ 0.83万
• 依托单位: Meiji University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 1999
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680365/
• 关键词: monotone DNF; duality; dualization; hypergraph; minimal transversal; polynomial time; space efficiency; 単調双対性; 横断ハイパーグラフ; DNF; 多項式時間アルゴリズム; 単調論理関数; 双対; 学習理論

The goal of this research project was to develop an algorithm for dualizing a boolean function given in DNF, that runs in time polynomial in the total size of the input and output. This problem is equivalent to the problem of generating all the minimal transversals of a given hypergraph. We were unable to achieve this ultimate goal. However, we discovered an algorithm for generating all the minimal transversals of a hypergraph using O (n log n) words of storage, where n is the size of the input hypergraph. The time complexity of this algorithm is quasi-polynomial and almost the same as the best known algorithm due to Fredman and Khachiyan. We have also discovered a polynomial time delay algorithm for generating all the minimal transversals of a given bounded-degree hypergraph.

该研究项目的目标是开发一种算法，用于对DNF中给出的布尔函数进行二元化，该算法在输入和输出的总大小中以时间多项式运行。这个问题等价于生成给定超图的所有最小断面的问题。我们无法实现这一最终目标。然而，我们发现了一个算法，用于生成所有的超图的最小断面使用O（n log n）字的存储，其中n是输入超图的大小。该算法的时间复杂度是拟多项式的，几乎与Fredman和Khachiyan提出的算法相同。我们还发现了一个多项式时间延迟算法，用于生成给定的有界度超图的所有最小横截。

项目成果

Hisao Tamaki: "Approximation algorithms for geometric optimization problems"IEICE Transaction on Information and Systems. E83-D, No.3. 455-461 (2000)

Hisao Tamaki：“几何优化问题的近似算法”IEICE Transaction on Information and Systems。

Hisao Tamaki: "Space-efficient enumeration of minimal transversals of a hypergraph"IPSJ Research Report. 2000-AL-75. 29-36 (2000)

Hisao Tamaki：“超图最小横截面的空间有效枚举”IPSJ 研究报告。

Qian-Ping Gu and Hisao Tamaki: "Multicolor routing in the undirected hypercube"Discrete Applied Mathematics. Vol.100 No.3. 169-181 (2000)

谷前平和玉木久雄：“无向超立方体中的多色路由”离散应用数学。

C.Papadimitriou, P.Raghavan, H.Tamaki, and S.Vempala: "Latent semantic indexing : a probalistic analysis"Journal of Computer and System Sciences. 61 (2). 217-235 (2000)

C.Papadimitriou、P.Raghavan、H.Tamaki 和 S.Vempala：“潜在语义索引：概率分析”计算机与系统科学杂志。

藤重(編): "離散構造とアルゴリズムVI(2章執筆)"近代科学社. 216 (1999)

Fujishige（编）：“离散结构和算法 VI（第 2 章）”Kindai Kagakusha 216（1999）。