APX とは

複雑さ理論では、クラスAPX(「近似可能」の略語)は、近似比が一定の(または一定の因子近似アルゴリズムで結ばれた)多項式時間近似アルゴリズムを可能にするNP最適化問題の集合である。簡単に言うと、このクラスの問題は、最適解の固定倍率内で解を見つけることができる効率的なアルゴリズムを持っています。
近似アルゴリズムは、アルゴリズムが求める解がせいぜい最適解よりも1倍倍の倍数であることが証明できれば、入力サイズ n {\displaystyle n} に対して f ( n ) {\displaystyle f(n)} 近似アルゴリズムと呼ばれます。ここで、 f ( n ) {\displaystyle f(n)} は近似比と呼ばれます。 APXにおける問題は、近似比 f ( n ) {\displaystyle f(n)} が定数 c {\displaystyle c} であるアルゴリズムを持つ問題である。近似率は通常1より大きいと言われている。最小化問題の場合、 f ( n ) {\displaystyle f(n)} は発見された解のスコアを最適解のスコアで割ったものであるが、最大化問題では逆の場合がある。最大解の問題について、劣った解がより小さいスコアを有する場合、 f ( n ) {\displaystyle f(n)} は時には1未満と表される。そのような場合、 f ( n ) {\displaystyle f(n)} の逆数は、最適解のスコアに対する発見された解のスコアの比です。
1以外のすべての乗法因子内で問題を解決するための多項式時間アルゴリズムがある場合、問題は多項式時間近似スキーム(PTAS)を有すると言われる。 P = NPでない限り、APXには存在するがPTASは存在しない問題が存在するため、PTASの問題のクラスはAPXに厳密に含まれています。そのような問題の1つはビン充填問題である。