「PTAS」の版間の差分

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

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

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

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

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

@@ 1行目: / 1行目: @@
 '''【ぴーてぃーえーえす (PTAS (polynomial time approximation scheme))】'''
-最小値が$<math>f(x^*)</math>$であるような関数最小化問題において, 任意の$<math>\alpha >0</math>$に対して
+最小値が<math>f(x^*)</math>であるような関数最小化問題において, 任意の<math>\alpha >0</math>に対して
+<br><center>
+<math>f(x)\leq (1+\alpha )f(x^*)</math>
+</center><br>
+となるような解<math>x</math>を(<math>\alpha</math>を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.
-<math>\[ f(x)\leq (1+\alpha )f(x^*) \]</math>
+[[category:近似・知能・感覚的手法|ぴーてぃーえーえす]]
-となるような解$<math>x</math>$を($<math>\alpha</math>$を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.