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