A Systematic Approach to Network Approximation Algorithms with Performance Guarantees

本研究的目的是从理论和实践的角度研究一种具有性能保证的网络逼近算法的系统方法，并阐明其对算法研究发展的有用性和约束，这对于本世纪的信息技术至关重要。为了实现这一目标，我们做了以下研究。我们对半定规划和线性规划技术进行了研究，这些技术被认为是设计和分析具有性能保证的网络逼近算法的潜在系统方法。更具体地说，我们通过翻译 V.V.Vazirani 撰写的《近似算法》一书以及 B.Korte 和 J.Vygen 撰写的《组合优化》一书来调查最近的趋势。这两本书被认为是描述世界上网络算法和逼近算法最新进展的最好的书。通过这次调查，我们获得了一些力量，并将这种力量应用于开发新的网络逼近算法。实际上，我们提出了MAX SAT当前最好的逼近算法。我们还提出了几种基于网络逼近算法的从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.