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

A Systematic Approach to Network Approximation Algorithms with Performance Guarantees

具有性能保证的网络逼近算法的系统方法

基本信息

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

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580389/
关键词：
Approximation Algorithms Network Algorithms NP-hard Linear Programming Semi-definite Programming

项目摘要

The objective of this research is to investigate a systematic approach to network approximation algorithms with performance guarantees from both theoretical and practical points of veiw and to clarify its usefulness and bound on the development of algorithmic researches which will be important for information technology in this centuary. To achive this objective, we have done the following researches.We made an investigation on semi-definite programming and linear programming techniques, which are considerd to be potential systematic approaches to designing and analyzing network approximation algorithms with performance guarantees.More specifically, we surveyed the recent trends by translating the book of Approximation Algorithms written by V.V.Vazirani and the book of Combinatorial Optimization written by B.Korte and J.Vygen. These two books are considered to be the best books describing the most recent progress in network algorithms and approximation algorithms in the world.Through this survey, we obtained some power and applied this power to developing new network approximation algorithms.Acutually, we proposed the current best approximation algorithm for MAX SAT.We also proposed several algorithms for exploiting inforamtion from the Web based on network approximation algorithms.These proposed algorithms were published in high standard international conferences and Journal.In view of this, we believe, the objective of this research is satisfactorily achieved.

本研究的目的是从理论和实践两个角度探讨一种系统的方法来研究具有性能保证的网络近似算法，并阐明其实用性和对算法研究发展的约束，这对本世纪的信息技术具有重要意义。为了实现这一目标，我们做了以下研究：我们研究了半定规划和线性规划技术，这些技术被认为是设计和分析具有性能保证的网络近似算法的潜在系统方法。我们通过翻译V.V.Vazirani写的《近似算法》一书和V.V.Vazirani写的《组合优化》一书，作者：B.Korte和J. Vygen。这两本书被认为是世界上描述网络算法和近似算法最新进展的最好的书，通过这次调查，我们获得了一些力量，并将这种力量应用于开发新的网络近似算法，实际上，提出了MAX SAT的最佳近似算法，并在此基础上提出了几种基于网络近似算法的Web信息挖掘算法，所提出的算法已在高标准的国际会议和杂志上发表，因此，我们相信，本研究的目的是令人满意地实现。