PTAS
2007年7月13日 (金) 00:54時点における122.17.2.240 (トーク)による版 (新しいページ: '【ぴーてぃーえーえす (PTAS (polynomial time approximation scheme))】 最小値が$f(x^*)$であるような関数最小化問題において, 任意の$\alpha >0$...')
【ぴーてぃーえーえす (PTAS (polynomial time approximation scheme))】
最小値が$f(x^*)$であるような関数最小化問題において, 任意の$\alpha >0$に対して
\[ f(x)\leq (1+\alpha )f(x^*) \]
となるような解$x$を($\alpha$を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.