| 翻訳と辞書 |
| APX-complete ： ウィキペディア英語版 |
APX
In complexity theory the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer. The class APX is also sometimes known as MaxSNP because the basis of its definition is formed by SNP.
An approximation algorithm is called a -approximation algorithm for input size if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of times worse than the optimal solution. Here, is called the ''approximation ratio''. Problems in APX are those with algorithms for which the approximation ratio is a constant . The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, is the found solution's score divided by the optimum solution's score, while for maximization problems the reverse is the case. For maximization problems, where an inferior solution has a smaller score, is sometimes stated as less than 1; in such cases, the reciprocal of is the ratio of the score of the found solution to the score of the optimum solution.
If there is a polynomial-time algorithm to solve a problem to within ''every'' multiplicative factor of the optimum other than 1, then the problem is said to have a polynomial-time approximation scheme (PTAS). Unless P=NP there exist problems that are in APX but without a PTAS, so the class of problems with a PTAS is strictly contained in APX. One such problem is the bin packing problem.
== APX-Hardness and APX-Completeness ==
A problem is said to be APX-hard if there is a PTAS reduction from every problem in APX to that problem, and to be APX-complete if the problem is APX-hard and also in APX. As a consequence of P ≠ NP ⇒ PTAS ≠ APX, P ≠ NP implies no APX-hard problem has a PTAS. In practice, reducing one problem to another to demonstrate APX-completeness is often done using other reduction schemes, such as L-reductions, which imply PTAS reductions.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「APX」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|