多項式時間近似スキーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/03 04:16 UTC 版)
計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。
- ^ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
- ^ 英: efficient polynomial-time approximation scheme
- ^ 英: fully polynomial-time approximation scheme
- ^ a b Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8
- ^ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer
- ^ 英: quasi-polynomial-time approximation scheme
- ^ 英: polynomial-time randomized approximation scheme
- ^ 英: efficient polynomial-time randomized approximation scheme
- ^ 英: fully polynomial-time randomized approximation scheme
[続きの解説]
「多項式時間近似スキーム」の続きの解説一覧
- 1 多項式時間近似スキームとは
- 2 多項式時間近似スキームの概要
- 3 変形
- 4 外部リンク
- 多項式時間近似スキームのページへのリンク
