近似アルゴリズム （きんじアルゴリズム、英 : approximation algorithm ）とは、組合せ最適化 問題の近似 解を得るためのアルゴリズム を言う[ 1] [ 2] [ 3] [ 4]
近似アルゴリズムの中でも、そのアルゴリズムの出力する解の目的関数値と最適解の目的関数値の比（近似度）がある範囲内に収まることが保証されているもののことを特に、精度保証付き近似アルゴリズムと呼ぶ。そのような保証のないアルゴリズムは発見的手法 （ヒューリスティクス）と呼ばれる。前者と後者を区別し、前者のみを近似アルゴリズムと呼ぶ場合もある。
近似アルゴリズムは、主に多項式時間 で厳密に解くことが難しいNP困難 問題に対して考えられるが、多項式時間で計算可能な問題に対しても、より早い計算時間で解を求めるという目的で用いられることもある。アルゴリズム理論 の分野においては近年の中心的話題のひとつで、さまざまな問題に対する近似アルゴリズムが考案されている。また、可能な近似度の下界値を示す近似不可能性に関する結果も多く得られており、PCP 定理などが有名。
例えば、最小頂点被覆問題 には近似度2の単純なアルゴリズムが存在するが、近似度が定数の多項式時間アルゴリズムがないと考えられている問題もある。
^ David P. Williamson; David B. Shmoys (2011). The Design of Approximation Algorithms . ISBN 978-0521195270 ^ V.V.ヴァジラーニ：「近似アルゴリズム」、丸善出版 (2012年7月17日)
^ J. ホロムコヴィッチ：「計算困難問題に対するアルゴリズム理論: 組合せ最適化・ランダマイゼ-ション・近似・ヒュ-リスティクス」、丸善出版 (2016年1月10日)
^ 浅野孝夫：「近似アルゴリズム: 離散最適化問題への効果的アプローチ」、共立出版、ISBN 978-4-320-12177-5 (2019年6月27日)
