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