In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems. The term L reduction is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - L-reduction (en)
- L-환산 (ko)
- L-redukcja (pl)
- Redução linear (pt)
- L-приведение (ru)
|
| rdfs:comment
| - In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems. The term L reduction is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept. (en)
- L-환산(L-reduction, linear reduction)은 최적화 문제 간의 근사 비율을 선형 보존하는 환산이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다. (ko)
- L-redukcja – transformacja problemów optymalizacyjnych, która zachowuje własności aproksymacyjne. L-redukcje odgrywają podobną rolę w badaniach nad aproksymowalnością problemów optymalizacyjnych, jak w badaniach nad złożonością obliczeniową problemów decyzyjnych. (pl)
- L-приведение (от «linear» = «линейное») — преобразование задач оптимизации, при которой линейно сохраняются свойства аппроксимации; является одним из видов . L-приведение в изучении возможности аппроксимации задач оптимизации играет похожую роль, какую играет при изучении вычислительной сложности задач разрешимости. Возможность L-приведения одной задачи к другой называется L-сводимостью. Термин «L-приведение» иногда используется для обозначения по аналогии с классом сложности L, но это совершенно другое понятие[уточнить]. (ru)
- Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação. Nos estudos de aproximação de problemas de otimização as reduções lineares desempenham um papel semelhante ao de reduções polinomiais no estudos da complexidade computacional de problemas de decisão. O termo L-redução é por vezes utilizado para se referir a reduções em espaço logarítmico, por analogia com a classe de complexidade L, mas isto é um conceito diferente. (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems. The term L reduction is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept. (en)
- L-환산(L-reduction, linear reduction)은 최적화 문제 간의 근사 비율을 선형 보존하는 환산이다. 여기에서 'L'의 의미는 선형(linear)을 가리킨다. (ko)
- L-redukcja – transformacja problemów optymalizacyjnych, która zachowuje własności aproksymacyjne. L-redukcje odgrywają podobną rolę w badaniach nad aproksymowalnością problemów optymalizacyjnych, jak w badaniach nad złożonością obliczeniową problemów decyzyjnych. (pl)
- L-приведение (от «linear» = «линейное») — преобразование задач оптимизации, при которой линейно сохраняются свойства аппроксимации; является одним из видов . L-приведение в изучении возможности аппроксимации задач оптимизации играет похожую роль, какую играет при изучении вычислительной сложности задач разрешимости. Возможность L-приведения одной задачи к другой называется L-сводимостью. Термин «L-приведение» иногда используется для обозначения по аналогии с классом сложности L, но это совершенно другое понятие[уточнить]. (ru)
- Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação. Nos estudos de aproximação de problemas de otimização as reduções lineares desempenham um papel semelhante ao de reduções polinomiais no estudos da complexidade computacional de problemas de decisão. O termo L-redução é por vezes utilizado para se referir a reduções em espaço logarítmico, por analogia com a classe de complexidade L, mas isto é um conceito diferente. (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)