权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Approximation Algorithms Based on Network Flow and Semidefinite Programming

基于网络流和半定规划的逼近算法

基本信息

批准号：
10205222
负责人：
ASANO Takao
金额：
$ 4.93万
依托单位：
Chuo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205222/
关键词：
Approximation algorithms Semidefinite programming Network flow Combinatorial optimization Maximum satisfiability Graph algorithms Minimum set cover Maximum independent set 近似率 VLSI設計 MAX SAT(最大充足化問題)MAX CUT(最大カット問題)ネットワークフロー設計

项目摘要

The objective of this research is to do research on approximation algorithms with high quality and high performance for combinatorial optimization problems based on network flow and semidefinite programming and contribute to the development of approximation algorithms from both theoretical and practical points of view. More specifically, we consider network problems and geometric problems including maximum satisfiability, maximum independent set, minimum set cover, VLSI physical design and so on, and obtain approximation algorithms with better performance based on network flow and semidefinite programming or on a newly proposed method. To achieve this objective, we have done the following researches.We made an investigation on important techniques developed for designing approximation algorithms which are of high qaulity and of high performance in the fields of computational geometry, graph-network algorithms, combinatorial optimization, parallel and distributed algorithms and so on. Especially based on the semidefinte programming and network-flow techniques, we made an investigation on discrete algorithms with high performance by exchanging ideas with leading researchers in the world. Through this investigation, we could propose approximation algorithms with high qaulity and high performance in the fields of VLSI design, information networks and real world applications. Specifically, for the maximum satisfiability problem, we proposed a new algorithm with the world best record in the performance. We also implemented the algorithms as well as algorithms previously proposed by other researchers with the helps of students and made computational experiments in order to evaluate the new algorithms not only from the theoretical point of view but also from the practical point of view. The results in this research were published in the world leading journals and symposia.

本研究的目的是研究基于网络流和半定规划的组合优化问题的高质量、高性能的近似算法，从理论和实践的角度为近似算法的发展做出贡献。更具体地说，我们考虑了网络问题和几何问题，包括最大可满足性、最大独立集、最小集覆盖、VLSI物理设计等，得到了基于网络流和半定规划或新提出的方法的性能更好的近似算法。为了实现这一目标，我们在计算几何、图网络算法、组合优化、并行和分布式算法等领域，研究了设计高质量、高性能近似算法的关键技术。特别是在半定规划和网络流技术的基础上，通过与国际上领先的研究人员交流思想，对高性能的离散算法进行了研究。通过这项研究，我们可以在VLSI设计、信息网络和实际应用中提出高质量和高性能的近似算法。具体地说，对于最大可满足性问题，我们提出了一种具有世界最好性能记录的新算法。我们还在学生的帮助下实现了算法以及其他研究人员提出的算法，并进行了计算实验，以便从理论和实践的角度对新算法进行评估。这项研究的结果发表在世界领先的期刊和研讨会上。