A Systematic Approach to Network Approximation Algorithms with Performance Guarantees

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

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.