APX (original) (raw)
En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la classe de complexitat APX és el conjunt dels problemes d'optimització a NP que tenen algorismes aproximats de temps polinòmic fitats per un factor d'aproximació que és una constat. En termes senzills, els problemes dins d'aquesta classe tenen algorismes prou eficients que donen una resposta amb un factor constant respecte a la solució òptima. Un algorisme aproximat s'anomena algorisme aproximat-f(n) per una entrada de mida n si es pot provar que la solució que troba aquest algorisme és almenys un factor f(n) pitjor que la solució òptima. A f(n) se'l denomina factor d'aproximació. Els problemes dins de la classe APX son aquells que la f(x) és una constant. (ca) 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 -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. 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. (en) En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr) Класс APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры, который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число. Аппроксимационный алгоритм называется алгоритмом c-аппроксимации с некоторой константой c, если можно доказать, что решение, полученное с помощью этого алгоритма, хуже оптимального не более чем в c раз. Константа c называется коэффициентом аппроксимации.В зависимости от того, является ли проблема проблемой максимизации или минимизации, решение может быть в c раз больше или в c раз меньше оптимального. К примеру, и задача о вершинном покрытии, и задача коммивояжёра с неравенством треугольника имеют простые алгоритмы, для которых c = 2.С другой стороны, доказано, что задачу коммивояжёра с произвольными длинами рёбер (не обязательно удовлетворяющими неравенству треугольника) нельзя аппроксимировать с постоянным коэффициентом, поскольку задачу поиска гамильтонова пути нельзя решить за полиномиальное время (в случае, если P ≠ NP). Если существует алгоритм решения задачи за полиномиальное время для любого фиксированного коэффициента большего единицы (один алгоритм для любого коэффициента), говорят, что задача имеет полиномиальную по времени схему аппроксимации (PTAS).Если P ≠ NP, можно показать, что существуют задачи, входящие в класс APX, но не в PTAS, то есть задачи, которые можно аппроксимировать с некоторым коэффициентом, но не с любым коэффициентом. Задача называется APX-трудной, если любая задача из класса APX имеет сведение к этой задаче, и APX-полной, если задача APX-трудна и сама принадлежит к классу APX.Из неравенства P ≠ NP следует, что PTAS ≠ APX, P ≠ NP, а отсюда никакая APX-трудная задача не принадлежит PTAS. Если задача APX-трудна, это обычно плохо, поскольку при P ≠ NP это означает отсутствие PTAS-алгоритма, который является наиболее полезным видом аппроксимационного алгоритма.Одна из наиболее простых APX-полных задач — это , вариант задачи выполнимости булевых формул.В этой задаче мы имеем булеву формулу в конъюнктивной нормальной форме, и хотим получить максимальное число подвыражений, которые будут выполняться при единственной подстановке значений true/false в переменные.Несмотря на то, что, скорее всего, задача не принадлежит PTAS, верное значение может быть получено с точностью 30 %, а некоторые упрощённые варианты задачи имеют PTAS. (ru) Em teoria da complexidade a classe 'APX' (uma abreviação de "aproximável" em inglês) é o conjunto de que permitem algoritmos de aproximação em com relação de aproximação delimitadas por uma constante (ou algoritmos de aproximação de fator constante por simplicidade). Em termos simples, problemas nessa classe tem algoritmos que podem encontrar uma resposta dentro de alguma porcentagem fixa da resposta ótima. Por exemplo, existe um algoritmo em tempo polinomial que encontra a solução para o problema que usa no máximo 5% mais do que o menor número possível de caixas. Um algoritmo de aproximação é chamado um c-algoritmo de aproximação para alguma constante c se puder ser provado que a solução que o algoritmo encontra é no máximo c vezes pior que a solução ótima. Aqui, c é chamado de relação de aproximação. Dependendo do problema ser uma minimalização ou maximização, isso pode denotar c vezes maior ou c vezes menor, respectivamente. Por exemplo, o problema da cobertura de vértices e o Problema do caixeiro-viajante (com desigualdade de triângulos) tem simples 2-algoritmos de aproximação cada. Em contraste, é provado que o problema do caixeiro-viajante com tamanhos de arestas arbitrários não podem ser aproximadas com relação de aproximação delimitadas por constante enquanto o problema de caminho hamiltoniano não puder ser resolvido em tempo polinomial, ou seja ao menos que P = NP. Se existe um algoritmo de tempo polinomial para resolver um problema no qual toda porcentagem fixa maior que zero (um algoritmo para cada porcentagem), então é dito que o problema tem um (polynomial-time approximation scheme ou PTAS em inglês). A menos que P=NP, pode ser mostrado que existem problemas que estão em APX mas não em PTAS; ou seja, problemas que podem ser aproximados dentro de alguma relação constante, mas não toda relação constante. Um problema é dito APX-difícil se existe alguma redução PTAS de cada problema em APX para tal problema, e é dito APX-completo se o problema é APX-difícil e também APX. Como consequência de P ≠ NP ⇒ PTAS ≠ APX, P ≠ NP ⇒ nenhum problema APX-difícil está em PTAS. Dizer que um problema é APX-difícil é geralmente uma notícia ruim, porque se P ≠ NP, isso nega a existência de uma PTAS, que é o tipo de algoritmo de aproximação mais útil. Um dos mais simples problemas APX-completos é o , uma variação do . Neste problema, temos uma fórmula em forma normal conjuntiva e queremos saber o número máximo de cláusulas que pode ser satisfeita simultâneamente por uma única atribuição de valores verdadeiro/falso para as variáveis. Apesar de que provavelmente ela não tem uma PTAS, ainda assim a resposta correta pode ser estimada dentro de 30% e algumas variantes simplificadas têm PTAS. (pt) Клас APX (від англ. approximable) у теорії обчислювальної складності — це клас NP-складних задач, для яких існують апроксимаційні алгоритми поліноміальної складності зі сталим коефіцієнтом апроксимації. У простіших термінах, задачі цього класу мають ефективні алгоритми, що знаходять розв'язки, які гірші від оптимального не більше ніж на фіксований відсоток. Наприклад, існує алгоритм поліноміальної складності для розв'язування задачі про пакування в ємності, який використовує не більше ніж на 5 % більше контейнерів, ніж найменша їх кількість. Апроксимаційний алгоритм називають алгоритмом c-апроксимації з деякою константою c, якщо можна довести, що розв'язок, отриманий за допомогою нього, гірший від оптимального не більше ніж у c разів. Константу c називають коефіцієнтом апроксимації. Залежно від того, чи є задача задачею максимізації чи мінімізації, розв'язок може бути в c разів більшим або в c разів меншим від оптимального. Наприклад, і задача про вершинне покриття, і задача комівояжера з нерівністю трикутника мають прості алгоритми, для яких c = 2. З іншого боку, доведено, що задачу комівояжера з довільними довжинами ребер (які не обов'язково задовольняють нерівності трикутника) не можна апроксимувати зі сталим коефіцієнтом, оскільки задачу пошуку гамільтонового шляху не можна розв'язати за поліноміальний час (у випадку, якщо P ≠ NP). Якщо існує алгоритм розв'язування задачі за поліноміальний час для будь-якого фіксованого коефіцієнта більшого від одиниці (один алгоритм для будь-якого коефіцієнта), кажуть, що задача має поліноміальну за часом схему апроксимації (PTAS) . Якщо P ≠ NP, можна показати, що існують задачі, що належать до класу APX, але не до PTAS, тобто задачі, які можна апроксимувати з деяким коефіцієнтом, але не з будь-яким коефіцієнтом. Задачу називають APX-складною, якщо будь-яка задача з класу APX має зведення до цієї задачі, і APX-повною, якщо задача APX-складна і сама належить до класу APX. З нерівності P ≠ NP випливає, що PTAS ≠ APX, P ≠ NP, а отже ніяка APX-складна задача не належить до PTAS. Якщо задача APX-складна, це зазвичай погано, оскільки при P ≠ NP це означає відсутність PTAS-алгоритму, який є найкориснішим видом апроксимаційного алгоритму. Одна з найпростіших APX-повних задач — це , варіант задачі здійсненності булевих формул. У цій задачі ми маємо в кон'юнктивній нормальній формі, і хочемо отримати найбільшу кількість підвиразів, які будуть виконуватися за єдиної підстановки значень true/false у змінні. Попри те, що, найпевніше, задача не належить до PTAS, правильне значення можна отримати з точністю 30 %, а деякі спрощені варіанти задачі мають PTAS. (uk) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20070405050438/http:/www.nada.kth.se/~viggo/wwwcompendium/ https://web.archive.org/web/20070413152307/http:/www.nada.kth.se/~viggo/wwwcompendium/node225.html http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.89.3995&rep=rep1&type=pdf http://www.nada.kth.se/%7Eviggo/wwwcompendium/ http://www.nada.kth.se/~viggo/wwwcompendium/node225.html |
| dbo:wikiPageID | 2018925 (xsd:integer) |
| dbo:wikiPageLength | 7639 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1040375348 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:MAX-3SAT dbr:Algorithm dbr:Approximation-preserving_reduction dbr:Approximation_algorithm dbr:Vertex_cover dbr:Independent_set_(graph_theory) dbr:L-reduction dbc:Approximation_algorithms dbr:Token_reconfiguration dbr:Conjunctive_normal_form dbr:Combinatorial_optimization dbr:Complexity_class dbr:Computational_complexity_theory dbr:PTAS_reduction dbr:Max/min_CSP/Ones_classification_theorems dbr:Travelling_salesman_problem dbr:Edge_coloring dbr:Gerhard_J._Woeginger dbc:Complexity_classes dbr:Marek_Karpinski dbr:Bin_packing_problem dbr:Dominating_set dbr:Boolean_satisfiability_problem dbr:Polynomial-time_approximation_scheme dbr:MaxSNP dbr:Optimization_problem dbr:Metric_(mathematics) dbr:P_=_NP_problem dbr:Polynomial-time |
| dbp:date | 2007-04-05 (xsd:date) 2007-04-13 (xsd:date) |
| dbp:url | https://web.archive.org/web/20070405050438/http:/www.nada.kth.se/~viggo/wwwcompendium/ https://web.archive.org/web/20070413152307/http:/www.nada.kth.se/~viggo/wwwcompendium/node225.html |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:Other_uses dbt:Short_description dbt:Webarchive dbt:ComplexityClasses dbt:CZoo |
| dcterms:subject | dbc:Approximation_algorithms dbc:Complexity_classes |
| rdf:type | yago:WikicatApproximationAlgorithms yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Class107997703 yago:Collection107951464 yago:Event100029378 yago:Group100031264 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant. Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial. Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP. (fr) En teoria de la complexitat, la classe de complexitat APX és el conjunt dels problemes d'optimització a NP que tenen algorismes aproximats de temps polinòmic fitats per un factor d'aproximació que és una constat. En termes senzills, els problemes dins d'aquesta classe tenen algorismes prou eficients que donen una resposta amb un factor constant respecte a la solució òptima. (ca) 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. (en) Em teoria da complexidade a classe 'APX' (uma abreviação de "aproximável" em inglês) é o conjunto de que permitem algoritmos de aproximação em com relação de aproximação delimitadas por uma constante (ou algoritmos de aproximação de fator constante por simplicidade). Em termos simples, problemas nessa classe tem algoritmos que podem encontrar uma resposta dentro de alguma porcentagem fixa da resposta ótima. Por exemplo, existe um algoritmo em tempo polinomial que encontra a solução para o problema que usa no máximo 5% mais do que o menor número possível de caixas. (pt) Класс APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры, который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число. (ru) Клас APX (від англ. approximable) у теорії обчислювальної складності — це клас NP-складних задач, для яких існують апроксимаційні алгоритми поліноміальної складності зі сталим коефіцієнтом апроксимації. У простіших термінах, задачі цього класу мають ефективні алгоритми, що знаходять розв'язки, які гірші від оптимального не більше ніж на фіксований відсоток. Наприклад, існує алгоритм поліноміальної складності для розв'язування задачі про пакування в ємності, який використовує не більше ніж на 5 % більше контейнерів, ніж найменша їх кількість. (uk) |
| rdfs:label | APX (en) APX (Complexitat) (ca) APX (complexité) (fr) Apx completude (pt) Класс APX (ru) Клас APX (uk) |
| owl:sameAs | freebase:APX yago-res:APX wikidata:APX dbpedia-ca:APX dbpedia-fr:APX dbpedia-he:APX dbpedia-pt:APX dbpedia-ru:APX dbpedia-uk:APX https://global.dbpedia.org/id/4KSUk |
| prov:wasDerivedFrom | wikipedia-en:APX?oldid=1040375348&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:APX |
| is dbo:wikiPageDisambiguates of | dbr:APX_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Max_SNP dbr:Poly-APX-complete dbr:Class_APX dbr:Poly-APX dbr:Constant-factor_approximation_algorithm dbr:Constant-factor_approximation_algorithms dbr:Constant_factor_approximation_algorithm dbr:Constant_ratio_approximation dbr:APX-complete dbr:APX-hard dbr:APX_(class) dbr:APX_complexity_class dbr:Log-APX |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Approximation-preserving_reduction dbr:Approximation_algorithm dbr:Cubic_graph dbr:Vertex_cover dbr:Independent_set_(graph_theory) dbr:Pebble_motion_problems dbr:Max_SNP dbr:Token_reconfiguration dbr:NYSE_Euronext dbr:Feedback_arc_set dbr:Feedback_vertex_set dbr:Hamiltonian_completion dbr:PTAS_reduction dbr:Max/min_CSP/Ones_classification_theorems dbr:MaxDDBS dbr:Maximum_satisfiability_problem dbr:Travelling_salesman_problem dbr:Graph_edit_distance dbr:Vertex_cycle_cover dbr:APX_(disambiguation) dbr:Wiener_connector dbr:Dominating_set dbr:Marketing_mix dbr:Boolean_satisfiability_problem dbr:Polynomial-time_approximation_scheme dbr:Canadian_traveller_problem dbr:SNP_(complexity) dbr:Exact_algorithm dbr:NP-hardness dbr:Poly-APX-complete dbr:Class_APX dbr:Poly-APX dbr:Constant-factor_approximation_algorithm dbr:Constant-factor_approximation_algorithms dbr:Constant_factor_approximation_algorithm dbr:Constant_ratio_approximation dbr:APX-complete dbr:APX-hard dbr:APX_(class) dbr:APX_complexity_class dbr:Log-APX |
| is foaf:primaryTopic of | wikipedia-en:APX |