| dbo:abstract
|
- In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem. (en)
- Na teoria da complexidade computacional, uma gap redução é uma redução de um tipo particular de problema de decisão, conhecido como problema de c-gap. Tais reduções fornecem informações sobre a dificuldade de aproximação de soluções para problemas de otimização. Em resumo, um problema de gap redução refere-se a uma redução onde o objetivo é distinguir entre os casos em que a melhor solução está acima de um limiar dos casos em que a melhor solução está abaixo de outro limiar, tal que os dois limiares tenham uma lacuna (gap) entre os dois. Gap reduções podem ser usadas para demonstrar resultados de não aproximação, como se um problema pode ser aproximado para um melhor fator de que o tamanho do gap, em seguida, o algoritmo de aproximação pode ser usado para resolver o correspondente problema da lacuna. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8283 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem. (en)
- Na teoria da complexidade computacional, uma gap redução é uma redução de um tipo particular de problema de decisão, conhecido como problema de c-gap. Tais reduções fornecem informações sobre a dificuldade de aproximação de soluções para problemas de otimização. Em resumo, um problema de gap redução refere-se a uma redução onde o objetivo é distinguir entre os casos em que a melhor solução está acima de um limiar dos casos em que a melhor solução está abaixo de outro limiar, tal que os dois limiares tenham uma lacuna (gap) entre os dois. Gap reduções podem ser usadas para demonstrar resultados de não aproximação, como se um problema pode ser aproximado para um melhor fator de que o tamanho do gap, em seguida, o algoritmo de aproximação pode ser usado para resolver o correspondente problema (pt)
|
| rdfs:label
|
- Gap reduction (en)
- Gap Redução (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is foaf:primaryTopic
of | |
