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.

这项研究的目的是研究一种系统的网络近似算法，具有VEIW的理论和实际点的性能保证，并阐明其有用性并限制了算法研究的开发，这对于本世纪的信息技术至关重要。 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和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算法。这些提议的算法发表在高标准的国际会议和期刊上。在此方面，这项研究的目的是令人满意的。