DBpedia – Linked Data Fragments

Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Approximation_algorithm> ?p ?o }

• Approximation_algorithm abstract "In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial-time exact algorithms solving NP-hard problems, one settles for polynomial-time sub-optimal solutions. Unlike heuristics, which usually only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run-time bounds. Ideally, the approximation is optimal up to a small constant factor (for instance within 5% of the optimal solution). Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size.A typical example for an approximation algorithm is the one for vertex cover in graphs: find an uncovered edge and add both endpoints to the vertex cover, until none remain. It is clear that the resulting cover is at most twice as large as the optimal one. This is a constant factor approximation algorithm with a factor of 2.NP-hard problems vary greatly in their approximability; some, such as the bin packing problem, can be approximated within any factor greater than 1 (such a family of approximation algorithms is often called a polynomial time approximation scheme or PTAS). Others are impossible to approximate within any constant, or even polynomial factor unless P = NP, such as the maximum clique problem.NP-hard problems can often be expressed as integer programs (IP) and solved exactly in exponential time. Many approximation algorithms emerge from the linear programming relaxation of the integer program.Not all approximation algorithms are suitable for all practical applications. They often use IP/LP/Semidefinite solvers, complex data structures or sophisticated algorithmic techniques which lead to difficult implementation problems. Also, some approximation algorithms have impractical running times even though they are polynomial time, for example O(n2156). Yet the study of even very expensive algorithms is not a completely theoretical pursuit as they can yield valuable insights. A classic example is the initial PTAS for Euclidean TSP due to Sanjeev Arora which had prohibitive running time, yet within a year, Arora refined the ideas into a linear time algorithm. Such algorithms are also worthwhile in some applications where the running times and cost can be justified e.g. computational biology, financial engineering, transportation planning, and inventory management. In such scenarios, they must compete with the corresponding direct IP formulations.Another limitation of the approach is that it applies only to optimization problems and not to \"pure\" decision problems like satisfiability, although it is often possible to conceive optimization versions of such problems, such as the maximum satisfiability problem (Max SAT).Inapproximability has been a fruitful area of research in computational complexity theory since the 1990 result of Feige, Goldwasser, Lovász, Safra and Szegedy on the inapproximability of Independent Set. After Arora et al. proved the PCP theorem a year later, it has now been shown that Johnson's 1974 approximation algorithms for Max SAT, Set Cover, Independent Set and Coloring all achieve the optimal approximation ratio, assuming P != NP.".
• Approximation_algorithm wikiPageExternalLink wwwcompendium.
• Approximation_algorithm wikiPageID "563105".
• Approximation_algorithm wikiPageLength "12503".
• Approximation_algorithm wikiPageOutDegree "56".
• Approximation_algorithm wikiPageRevisionID "702632463".
• Approximation_algorithm wikiPageWikiLink APX.
• Approximation_algorithm wikiPageWikiLink Algorithm.
• Approximation_algorithm wikiPageWikiLink Approximation-preserving_reduction.
• Approximation_algorithm wikiPageWikiLink Approximation_Algorithms_for_NP-Hard_problems.
• Approximation_algorithm wikiPageWikiLink Bin_packing_problem.
• Approximation_algorithm wikiPageWikiLink Boolean_satisfiability_problem.
• Approximation_algorithm wikiPageWikiLink Cambridge_University_Press.
• Approximation_algorithm wikiPageWikiLink Category:Approximation_algorithms.
• Approximation_algorithm wikiPageWikiLink Category:Computational_complexity_theory.
• Approximation_algorithm wikiPageWikiLink Charles_E._Leiserson.
• Approximation_algorithm wikiPageWikiLink Clifford_Stein.
• Approximation_algorithm wikiPageWikiLink Clique_problem.
• Approximation_algorithm wikiPageWikiLink Computational_biology.
• Approximation_algorithm wikiPageWikiLink Computer_science.
• Approximation_algorithm wikiPageWikiLink Convex_optimization.
• Approximation_algorithm wikiPageWikiLink Decision_problem.
• Approximation_algorithm wikiPageWikiLink Domination_analysis.
• Approximation_algorithm wikiPageWikiLink Dorit_S._Hochbaum.
• Approximation_algorithm wikiPageWikiLink Dynamic_programming.
• Approximation_algorithm wikiPageWikiLink Exact_algorithm.
• Approximation_algorithm wikiPageWikiLink Financial_engineering.
• Approximation_algorithm wikiPageWikiLink Gerhard_J._Woeginger.
• Approximation_algorithm wikiPageWikiLink Graph_(discrete_mathematics).
• Approximation_algorithm wikiPageWikiLink Greedy_algorithm.
• Approximation_algorithm wikiPageWikiLink Heuristic_(computer_science).
• Approximation_algorithm wikiPageWikiLink Independent_set_(graph_theory).
• Approximation_algorithm wikiPageWikiLink Introduction_to_Algorithms.
• Approximation_algorithm wikiPageWikiLink Johan_Håstad.
• Approximation_algorithm wikiPageWikiLink Linear_programming.
• Approximation_algorithm wikiPageWikiLink Linear_programming_relaxation.
• Approximation_algorithm wikiPageWikiLink Local_search_(optimization).
• Approximation_algorithm wikiPageWikiLink MAX-3SAT.
• Approximation_algorithm wikiPageWikiLink Marek_Karpinski.
• Approximation_algorithm wikiPageWikiLink Maximum_satisfiability_problem.
• Approximation_algorithm wikiPageWikiLink NP-hardness.
• Approximation_algorithm wikiPageWikiLink Operations_research.
• Approximation_algorithm wikiPageWikiLink Optimization_problem.
• Approximation_algorithm wikiPageWikiLink PCP_theorem.
• Approximation_algorithm wikiPageWikiLink P_versus_NP_problem.
• Approximation_algorithm wikiPageWikiLink Polynomial-time_approximation_scheme.
• Approximation_algorithm wikiPageWikiLink Ron_Rivest.
• Approximation_algorithm wikiPageWikiLink Sanjeev_Arora.
• Approximation_algorithm wikiPageWikiLink Semidefinite_programming.
• Approximation_algorithm wikiPageWikiLink Stock_management.
• Approximation_algorithm wikiPageWikiLink Thomas_H._Cormen.
• Approximation_algorithm wikiPageWikiLink Time_complexity.
• Approximation_algorithm wikiPageWikiLink Transportation_planning.
• Approximation_algorithm wikiPageWikiLink Travelling_salesman_problem.
• Approximation_algorithm wikiPageWikiLink Vertex_cover.
• Approximation_algorithm wikiPageWikiLinkText "Approximation algorithm".
• Approximation_algorithm wikiPageWikiLinkText "Approximation".
• Approximation_algorithm wikiPageWikiLinkText "Approximations".
• Approximation_algorithm wikiPageWikiLinkText "Near-optimization".
• Approximation_algorithm wikiPageWikiLinkText "approximability".
• Approximation_algorithm wikiPageWikiLinkText "approximate".
• Approximation_algorithm wikiPageWikiLinkText "approximated".
• Approximation_algorithm wikiPageWikiLinkText "approximately solving".
• Approximation_algorithm wikiPageWikiLinkText "approximately".
• Approximation_algorithm wikiPageWikiLinkText "approximates".
• Approximation_algorithm wikiPageWikiLinkText "approximating".
• Approximation_algorithm wikiPageWikiLinkText "approximation algorithm".
• Approximation_algorithm wikiPageWikiLinkText "approximation algorithms".
• Approximation_algorithm wikiPageWikiLinkText "approximation problems".
• Approximation_algorithm wikiPageWikiLinkText "approximation ratio".
• Approximation_algorithm wikiPageWikiLinkText "approximation".
• Approximation_algorithm wikiPageWikiLinkText "approximations".
• Approximation_algorithm wikiPageWikiLinkText "c-approximating".
• Approximation_algorithm wikiPageWikiLinkText "constant factor approximation".
• Approximation_algorithm wikiPageWikiLinkText "performance guarantee".
• Approximation_algorithm wikiPageWikiLinkText "performance".
• Approximation_algorithm wikiPageWikiLinkText "ε-approximated".
• Approximation_algorithm wikiPageUsesTemplate Template:Authority_control.
• Approximation_algorithm wikiPageUsesTemplate Template:Citation.
• Approximation_algorithm wikiPageUsesTemplate Template:Cite_book.
• Approximation_algorithm wikiPageUsesTemplate Template:More_footnotes.
• Approximation_algorithm wikiPageUsesTemplate Template:Optimization_algorithms.
• Approximation_algorithm wikiPageUsesTemplate Template:Reflist.
• Approximation_algorithm subject Category:Approximation_algorithms.
• Approximation_algorithm subject Category:Computational_complexity_theory.
• Approximation_algorithm hypernym Algorithms.
• Approximation_algorithm type Algorithm.
• Approximation_algorithm type Diacritic.
• Approximation_algorithm type Redirect.
• Approximation_algorithm type Thing.
• Approximation_algorithm comment "In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial-time exact algorithms solving NP-hard problems, one settles for polynomial-time sub-optimal solutions.".
• Approximation_algorithm label "Approximation algorithm".
• Approximation_algorithm sameAs Q621751.
• Approximation_algorithm sameAs Aproximační_algoritmy.
• Approximation_algorithm sameAs Approximationsalgorithmus.
• Approximation_algorithm sameAs Algoritmo_de_aproximación.
• Approximation_algorithm sameAs الگوریتم_تقریبی.
• Approximation_algorithm sameAs Algorithme_dapproximation.
• Approximation_algorithm sameAs אלגוריתם_קירוב.
• Approximation_algorithm sameAs Algoritmo_di_approssimazione.

• next