Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Gap_reduction> ?p ?o }
Showing triples 1 to 28 of
28
with 100 triples per page.
- Gap_reduction 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.".
- Gap_reduction wikiPageID "44640690".
- Gap_reduction wikiPageLength "7587".
- Gap_reduction wikiPageOutDegree "17".
- Gap_reduction wikiPageRevisionID "639179149".
- Gap_reduction wikiPageWikiLink Approximation-preserving_reduction.
- Gap_reduction wikiPageWikiLink Approximation_algorithm.
- Gap_reduction wikiPageWikiLink Boolean_satisfiability_problem.
- Gap_reduction wikiPageWikiLink Category:Approximation_algorithms.
- Gap_reduction wikiPageWikiLink Category:Computational_problems.
- Gap_reduction wikiPageWikiLink Computational_complexity_theory.
- Gap_reduction wikiPageWikiLink Hamiltonian_path.
- Gap_reduction wikiPageWikiLink Metric_(mathematics).
- Gap_reduction wikiPageWikiLink Optimization_problem.
- Gap_reduction wikiPageWikiLink PTAS_reduction.
- Gap_reduction wikiPageWikiLink Reduction_(complexity).
- Gap_reduction wikiPageWikiLink Travelling_salesman_problem.
- Gap_reduction wikiPageUsesTemplate Template:Reflist.
- Gap_reduction wikiPageUsesTemplate Template:Technical.
- Gap_reduction subject Category:Approximation_algorithms.
- Gap_reduction subject Category:Computational_problems.
- Gap_reduction hypernym Reduction.
- Gap_reduction type Album.
- Gap_reduction 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_reduction label "Gap reduction".
- Gap_reduction sameAs m.012g48r6.
- Gap_reduction wasDerivedFrom Gap_reduction?oldid=639179149.
- Gap_reduction isPrimaryTopicOf Gap_reduction.