Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Approximation_algorithm> ?p ?o. }
Showing items 1 to 43 of
43
with 100 items per page.
- 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(n2000). 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, Lovasz, 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 wikiPageRevisionID "583541912".
- Approximation_algorithm hasPhotoCollection Approximation_algorithm.
- Approximation_algorithm subject Category:Approximation_algorithms.
- Approximation_algorithm subject Category:Computational_complexity_theory.
- Approximation_algorithm type Abstraction100002137.
- Approximation_algorithm type Act100030358.
- Approximation_algorithm type Activity100407535.
- Approximation_algorithm type Algorithm105847438.
- Approximation_algorithm type ApproximationAlgorithms.
- Approximation_algorithm type Event100029378.
- Approximation_algorithm type Procedure101023820.
- Approximation_algorithm type PsychologicalFeature100023100.
- Approximation_algorithm type Rule105846932.
- Approximation_algorithm type YagoPermanentlyLocatedEntity.
- 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 "Algorithme d'approximation".
- Approximation_algorithm label "Algoritmo de aproximación".
- Approximation_algorithm label "Algoritmo de aproximação".
- Approximation_algorithm label "Algoritmo di approssimazione".
- Approximation_algorithm label "Algorytm aproksymacyjny".
- Approximation_algorithm label "Approximation algorithm".
- Approximation_algorithm label "Approximationsalgorithmus".
- Approximation_algorithm label "Аппроксимационный алгоритм".
- Approximation_algorithm label "近似アルゴリズム".
- Approximation_algorithm label "近似算法".
- Approximation_algorithm sameAs Aproximační_algoritmy.
- Approximation_algorithm sameAs Approximationsalgorithmus.
- Approximation_algorithm sameAs Algoritmo_de_aproximación.
- Approximation_algorithm sameAs Algorithme_d'approximation.
- Approximation_algorithm sameAs Algoritmo_di_approssimazione.
- Approximation_algorithm sameAs 近似アルゴリズム.
- Approximation_algorithm sameAs 근사_알고리즘.
- Approximation_algorithm sameAs Algorytm_aproksymacyjny.
- Approximation_algorithm sameAs Algoritmo_de_aproximação.
- Approximation_algorithm sameAs m.02qc78.
- Approximation_algorithm sameAs Q621751.
- Approximation_algorithm sameAs Q621751.
- Approximation_algorithm sameAs Approximation_algorithm.
- Approximation_algorithm wasDerivedFrom Approximation_algorithm?oldid=583541912.
- Approximation_algorithm isPrimaryTopicOf Approximation_algorithm.