Matches in DBpedia 2014 for { <http://dbpedia.org/resource/PTAS_reduction> ?p ?o. }
Showing items 1 to 13 of
13
with 100 items per page.
- PTAS_reduction abstract "In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write .With ordinary polynomial-time many-one reductions, if we can describe a reduction from a problem A to a problem B, then any polynomial-time solution for B can be composed with that reduction to obtain a polynomial-time solution for the problem A. Similarly, our goal in defining PTAS reductions is so that given a PTAS reduction from an optimization problem A to a problem B, a PTAS for B can be composed with the reduction to obtain a PTAS for the problem A.Formally, we define a PTAS reduction from A to B using three polynomial-time computable functions, f, g, and α, with the following properties: f maps instances of problem A to instances of problem B. g takes an instance x of problem A, an approximate solution to the corresponding problem in B, and an error parameter ε and produces an approximate solution to x. α maps error parameters for solutions to instances of problem A to error parameters for solutions to problem B. If the solution y to (an instance of problem B) is at most times worse than the optimal solution, then the corresponding solution to x (an instance of problem A) is at most times worse than the optimal solution.From this definition it is straightforward to show that: and and and".
- PTAS_reduction wikiPageExternalLink books?vid=ISBN3540210458.
- PTAS_reduction wikiPageID "9010084".
- PTAS_reduction wikiPageRevisionID "491566153".
- PTAS_reduction hasPhotoCollection PTAS_reduction.
- PTAS_reduction subject Category:Computational_complexity_theory.
- PTAS_reduction comment "In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX.".
- PTAS_reduction label "PTAS reduction".
- PTAS_reduction sameAs m.027t9lx.
- PTAS_reduction sameAs Q7120941.
- PTAS_reduction sameAs Q7120941.
- PTAS_reduction wasDerivedFrom PTAS_reduction?oldid=491566153.
- PTAS_reduction isPrimaryTopicOf PTAS_reduction.