「PTAS」の版間の差分

2007年7月13日 (金) 11:07時点における版

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

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

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

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

@@ 2行目: / 2行目: @@
 最小値が$<math>f(x^*)</math>$であるような関数最小化問題において, 任意の$<math>\alpha >0</math>$に対して
+<br><center>
-<math>\[ f(x)\leq (1+\alpha )f(x^*) \]</math>
+<math>f(x)\leq (1+\alpha )f(x^*)</math>
+</center><br>
 となるような解$<math>x</math>$を($<math>\alpha</math>$を定数とみなしたとき)多項式時間で求めることのできるアルゴリズム. 最大化の場合は対称的に考える.