Matches in DBpedia 2015-10 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 "12442".
- Approximation_algorithm wikiPageOutDegree "54".
- Approximation_algorithm wikiPageRevisionID "681743643".
- 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 Constant_factor_approximation_algorithm.
- Approximation_algorithm wikiPageWikiLink Convex_optimization.
- Approximation_algorithm wikiPageWikiLink Convex_programming.
- Approximation_algorithm wikiPageWikiLink Decision_problem.
- Approximation_algorithm wikiPageWikiLink Domination_analysis.
- Approximation_algorithm wikiPageWikiLink Dorit_S._Hochbaum.
- Approximation_algorithm wikiPageWikiLink Dynamic_programming.
- Approximation_algorithm wikiPageWikiLink Euclidean_traveling_salesman_problem.
- Approximation_algorithm wikiPageWikiLink Exponential_time.
- Approximation_algorithm wikiPageWikiLink Financial_engineering.
- Approximation_algorithm wikiPageWikiLink Gerhard_J._Woeginger.
- Approximation_algorithm wikiPageWikiLink Graph_(mathematics).
- Approximation_algorithm wikiPageWikiLink Greedy_algorithm.
- Approximation_algorithm wikiPageWikiLink Heuristic_(computer_science).
- Approximation_algorithm wikiPageWikiLink Independent_set_(graph_theory).
- Approximation_algorithm wikiPageWikiLink Integer_programs.
- Approximation_algorithm wikiPageWikiLink Introduction_to_Algorithms.
- Approximation_algorithm wikiPageWikiLink Inventory_management.
- 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_clique_problem.
- Approximation_algorithm wikiPageWikiLink Maximum_satisfiability_problem.
- Approximation_algorithm wikiPageWikiLink NP-hard.
- Approximation_algorithm wikiPageWikiLink NP-hardness.
- Approximation_algorithm wikiPageWikiLink Operations_research.
- Approximation_algorithm wikiPageWikiLink Optimization_problem.
- Approximation_algorithm wikiPageWikiLink PCP_theorem.
- Approximation_algorithm wikiPageWikiLink P_=_NP.
- Approximation_algorithm wikiPageWikiLink P_versus_NP_problem.
- Approximation_algorithm wikiPageWikiLink Polynomial-time_approximation_scheme.
- Approximation_algorithm wikiPageWikiLink Polynomial_time.
- Approximation_algorithm wikiPageWikiLink Polynomial_time_approximation_scheme.
- Approximation_algorithm wikiPageWikiLink Ron_Rivest.
- Approximation_algorithm wikiPageWikiLink Ronald_L._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 wikiPageWikiLink Vertex_cover_problem.
- 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 hasPhotoCollection Approximation_algorithm.
- 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 Article.