PCP and Hardness of Approximation(Luca)

Lecture 1

pcp-history

简单介绍hardness of approximation。
数以百计的有趣且重要的组合优化问题都是NP-hard的,而且任何一个都没有一个最差情形的准确的算法来解决。除了证明P=NP,当我们遇到一个NP-hard问题时,我们肯定要接受对一个多项式时间的最优算法的一个或者多个前提的松弛。可行的对付NP-hardness的方式有如下几种:

  • 在温和的指数时间内运行,如O(1.1^n)
  • 在多项式时间内运行在典型的实例上。这类算法在实践中有效。因为对典型这一概念给出一个满意的形式化的处理方式是比较困难的,所以对于这类算法符合要求的理论上处理的方式较难理解。(大多数对算法平均情形的分析是基于输入的分布的,这一假设在实践中是有较大差异的)
  • 在多项式时间内在所有的输入上运行,只是返回一个以一定代价靠近最优解次优解。
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s