NP完全問題
英語の頭文字をとってTSPともいう。 n {\displaystyle n} 個の点をもつ完全グラフ G {\displaystyle G} と、 G {\displaystyle G} の任意の辺 e {\displaystyle e} に対する非負の重み w e {\displaystyle w_{e}} と上限 D {\displaystyle D} が与えられる。このとき重みの総和が高々 D {\displaystyle D} であるような G {\displaystyle G} のハミルトン閉路は存在するか?という問題。この問題の最適化版(できるだけ重みが小さなハミルトン路を求める)は、P=NPでない限りいかなる定数近似アルゴリズムも持たないことが知られている。辺重みが三角不等式を満たしているような特別な場合には、1.5-近似アルゴリズム(Christofidesのアルゴリズム)が知られている。
品物の集合 J = { j 1 , ... , j n } {\displaystyle J=\{j_{1},\ldots ,j_{n}\}} とその価値 p j ( j ∈ J ) {\displaystyle p_{j}\;(j\in J)} と重み w j ( j ∈ J ) {\displaystyle w_{j}\;(j\in J)} とナップサックの容量 W {\displaystyle W} と要求量 D {\displaystyle D} が与えられる。 J {\displaystyle J} の部分集合 U {\displaystyle U} はそのなかの品物の重みの総和が W {\displaystyle W} 以下であるとき許容できると言われる。このとき、許容できる集合 U {\displaystyle U} であって、そのなかの品物の価値の総和が D {\displaystyle D} 以上になるようなものは存在するか?という問題。この問題の最適化版(できるだけ価値が大きな許容できる部分集合を求める)は、多項式時間近似スキーム(PTAS)を持つ。つまり任意の正の数 0 < ε ≤ 1 {\displaystyle 0<\epsilon \leq 1} に対して、 ( 1 − ε ) {\displaystyle (1-\epsilon )} -近似アルゴリズムが存在する。