Approximation Algorithms for Combinatorial Optimization Problems

组合优化问题的近似算法

• 批准号: 10205208
• 负责人: HIRATA Tomio
• 金额: $ 6.72万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205208/
• 关键词: approximating algorithms; via minimization; distance transform; net assignment; edge dominating set; morphological filter; petri-net; レイアウト設計; 最大カット問題; 充足最大化問題; 半定値計画法; 摂動

The purpose of this research is to design approximation algorithms for various combinatorial optimization problems and to analyze their approximation ratios.The results obtained are as follows.(1) 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.(2) We proposed an algorithm for the minimization of the number of vias in the VLSI layout design.(3) We designed an efficient algorithm for the Euclidean distance transform and give an uniform method for morphlogical operations in picture processing.(4) Approximability of edge dominating set problem and its related ones are also investigated.

本研究的目的是设计各种组合优化问题的逼近算法并分析其逼近率。得到的结果如下：(1)针对逻辑仿真器中的网络分配问题设计了一种高效的算法，用于(2)我们提出了一种在VLSI布局设计中最小化通孔数量的算法。(3)我们设计了一种有效的欧几里德距离变换算法，并给出了一种统一的方法(4)研究了边缘支配集问题及其相关问题的逼近性。

项目成果

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

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

T.Hirata and T.Ono: "Approximation Algorithms for MAXSAT"IEICE Trans. on Information and Systems. Vol.E83-D, No.3. 488-495 (2000)

T.Hirata 和 T.Ono：“MAXSAT 的近似算法”IEICE Trans。

Toshihiro Fujito: "A Unified Approximation Algorithm for Node-Deletion Problems" Discrete Applied Mathematics. Vol.86. 213-231 (1998)

Toshihiro Fujito：“节点删除问题的统一近似算法”离散应用数学。

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

T.Ono 和 T.Hirata：“网络分配问题的改进算法”IEICE Trans。

N.Iso, T.Hirata: "Implementation of Routability Checking Algorithm for Planar Layouts"IEICE Trans.on Information and Systems. Vol.40No.4. 1636-1643 (1999)

N.Iso、T.Hirata：“平面布局的可布线性检查算法的实现”IEICE Trans.on 信息和系统。