Definitions for APX
apx

WikipediaRate this definition:0.0 / 0 votes

1. APX

   In computational 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. An approximation algorithm is called an f ( n ) {\displaystyle f(n)} -approximation algorithm for input size n {\displaystyle n} if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f ( n ) {\displaystyle f(n)} times worse than the optimal solution. Here, f ( n ) {\displaystyle f(n)} is called the approximation ratio. Problems in APX are those with algorithms for which the approximation ratio f ( n ) {\displaystyle f(n)} is a constant c {\displaystyle c} . The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, f ( n ) {\displaystyle f(n)} 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, f ( n ) {\displaystyle f(n)} is sometimes stated as less than 1; in such cases, the reciprocal of f ( n ) {\displaystyle f(n)} is the ratio of the score of the found solution to the score of the optimum solution. A problem is said to have a polynomial-time approximation scheme (PTAS) if for every multiplicative factor of the optimum worse than 1 there is a polynomial-time algorithm to solve the problem to within that factor. 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.

WikidataRate this definition:0.0 / 0 votes

1. APX

   In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed percentage of the optimal answer. For example, there is a polynomial-time algorithm which will find a solution to the bin packing problem that uses at most 5% more than the smallest possible number of bins. An approximation algorithm is called a c-approximation algorithm for some constant c if it can be proven that the solution that the algorithm finds is at most c times worse than the optimal solution. Here, c is called the approximation ratio. Depending on whether the problem is a minimization or a maximization problem, this can either denote c times larger or c times smaller, respectively. For example, the vertex cover problem and traveling salesman problem with triangle inequality each have simple 2-approximation algorithms. In contrast, it's proven that the traveling salesman problem with arbitrary edge-lengths can not be approximated with approximation ratio bounded by a constant as long as the Hamiltonian-path problem can not be solved in polynomial time, that is unless P = NP.

Suggested ResourcesRate this definition:0.0 / 0 votes

1. apx

   Song lyrics by apx -- Explore a large variety of song lyrics performed by apx on the Lyrics.com website.

2. APX

   What does APX stand for? -- Explore the various meanings for the APX acronym on the Abbreviations.com website.

How to pronounce APX?

1. Alex

   US English

   David

   US English

   Mark

   US English

   Daniel

   British

   Libby

   British

   Mia

   British

   Karen

   Australian

   Hayley

   Australian

   Natasha

   Australian

   Veena

   Indian

   Priya

   Indian

   Neerja

   Indian

   Zira

   US English

   Oliver

   British

   Wendy

   British

   Fred

   US English

   Tessa

   South African

How to say APX in sign language?

Numerology

1. Chaldean Numerology

   The numerical value of APX in Chaldean Numerology is: 5

2. Pythagorean Numerology

   The numerical value of APX in Pythagorean Numerology is: 5

Popularity rank by frequency of use

References

1. ^ Wikipedia
   https://en.wikipedia.org/wiki/Apx
2. ^ Wikidata
   https://www.wikidata.org/w/index.php?search=APX