「PTAS」の版間の差分

2008年11月5日 (水) 16:53時点における最新版

【ぴーてぃーえーえす (PTAS (polynomial time approximation scheme))】

最小値が $f(x^{*})$ であるような関数最小化問題において, 任意の $\alpha >0$ に対して

$f(x)\leq (1+\alpha )f(x^{*})$

となるような解 $x$ を( $\alpha$ を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.

@@ 6行目: / 6行目: @@
 </center><br>
 となるような解<math>x</math>を(<math>\alpha</math>を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.
+[[category:近似・知能・感覚的手法|ぴーてぃーえーえす]]