A Study of Approximation Algorithms for Combinatorial Optimization Problems

组合优化问题的逼近算法研究

• 批准号: 10680350
• 负责人: HIRATA Tomio
• 金额: $ 1.86万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680350/
• 关键词: approximation algorithm; satisfiability problem; max cut; edge dominating set; layout design; logic emulator; 距離変換; ネット割り当て問題; 辺支配集合問題; ペトリネット; 頂点除去問題; マトロイド; 充足最大化問題; 判定値計画法; 摂動

The purpose of this research is to develop efficient approximation algorithms with high performance ratio for various combinatorial optimization problems. The problems we treat includes the satisfiability of a Boolean expression (MAX SAT), the maximum cut of a graph (MAX CUT) and the edge-dominating set of a graph. Since these problems are all NP-hard, it is theoretically, as well as practically, important to develop approximation algorithms with high performance ratio.The results obtained are as follows. We introduced perturbation on a truth assignment and obtained a better algorithm for MAX SAT.We proposed an algorithm for the minimization of vias in the VLSI layout design. We designed an efficient algorithm for the Euclidean distance transform and gave an uniform method for morphology operations in picture processing. We designed an efficient algorithm for the net assignment problem in logic emulator, which is used for logic verification process in designing large scale circuits. Furthermore, approximability of the edge dominating set problem and its related ones are also investigated.

本研究的目的是针对各种组合优化问题开发具有高性能的高效近似算法。我们处理的问题包括布尔表达式的可满足性（MAX SAT）、图的最大割（MAX CUT）和图的边支配集。由于这些问题都是NP难问题，因此开发高性能的近似算法无论在理论上还是在实践上都具有重要意义。得到的结果如下。我们引入了对真值分配的扰动，并获得了更好的 MAX SAT 算法。我们提出了一种在 VLSI 布局设计中最小化通孔的算法。我们设计了一种有效的欧氏距离变换算法，并给出了图像处理中形态学操作的统一方法。我们针对逻辑仿真器中的网络分配问题设计了一种有效的算法，用于设计大规模电路时的逻辑验证过程。此外，还研究了边缘支配集问题及其相关问题的近似性。

项目成果

Toshihiro Fujito: "On Approximation of the Submodular Set Cover Problem"Operations Reseach Letters. Vol.25 No.4. 169-174 (1999)

Toshihiro Fujito：“关于子模集覆盖问题的近似”操作研究快报。

T.Ono, T.Hirata: "An Improved Algorithm for the Net Assignment Problem"IEICE Trans.on Fundamentals. Vol.E84-A, No.5(to appear). (2001)

T.Ono、T.Hirata：“网络分配问题的改进算法”IEICE Trans.on 基础知识。

T.Fujito: "Approximation Algorithms for Submodular Set Cover with Applications"IEICE Trans.on Inf.& Syst.. Vol.E83-D, No.3. 170-177 (2000)

T.Fujito：“子模集覆盖的近似算法及其应用”IEICE Trans.on Inf.

磯直行,平田富夫: ""平面配線可能性検証アルゴリズムの実現""情報処理学会論文誌. Vol.40 No.4. 1636-1643 (1999)

Naoyuki Iso、Tomio Hirata：“平面布线可行性验证算法的实现”日本信息处理学会交易第 40 卷第 1636-1643 期（1999 年）。

A.Sakurai, T.Hirata: "On a Class of Efficiently Computable Morphological filters"Trans.IPSJ. Vol.41, No.12. 3344-3351 (2000)

A.Sakurai、T.Hirata：“关于一类高效可计算的形态过滤器”Trans.IPSJ。