逼近演算法之設計與分析

Abstract

演算法自計算機科學發展以來一直是核心研究中的一部分，而其中最佳化問題算法的 演進也都是重要的議題。本計晝的三個主題在：

一、為特定的算法問題設計有效率的逼近算法或進行average case complexity的分 析：

在P关NP幾近成立的前提下，許多屬於NP-Hard但重要而常用來建模的算法 問題要有效率的完美求解已是希望渺茫。進而解決此類問題的方向便是進行逼近 算法的研究或者分析在average case下，問題是否會變得容易許多。面對有多項 式時間算法但仍希望增進時間效率的情況，也可以嘗試放寬求解的質量進而設計 高效算法。

二、分析問題的不可逼近性：

面對逼近算法也難以設計的情況下，必須從另一方面探討問題可逼近的極限，是 否連逼近本身也是真正困難的。

三、問題的計算複雜度歸類：

許多問題雖然可能已知是NP-Hard，但詳細應被歸類在哪還未有結果，在對於算法 問題的算法設計與結構上的仔細分析後會對問題的本質有更多的了解，有助於我 們將尚未歸類的難題作分類。進一步了解問題的困難度。

The design and analysis of algorithms has been the central topic of computer science, since the very beginning of this field. Although there is no proof of P^NP, we believe there are many problems that cannot be solved in polynomial time. Thus the idea of approximation algorithms comes to play. In this project we will propose to investigate the following three issues:

1. Design efficient approximation algorithms for specific optimization problems and give average case analyses, etc. instead of worst case analysis.

2. Investigate the in-approximality of optimization problems. Improve the ratio of approximation of specific problems.

3. Furthermore, since we know some problems are in-approximable within some factor unless P=NP. We can study the more accurate higher order class, such as Sigma_2 or Pi_2, that the in-approximable problem should belong to.