inapproximability

inapproximability
a) The condition of being inapproximable
b) The exten to to which something is inapproximable

Wikipedia foundation.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Maximum cut — A maximum cut. For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max cut problem. The problem can be stated simply as follows. One wants a subset… …   Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

  • 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

  • Approximation algorithm — 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 …   Wikipedia

  • Domination analysis — of an approximation algorithm is a way to estimate its performance, introduced by Glover and Punnen in 1997. Unlike the classical approximation ratio analysis, which compares the numerical quality of a calculated solution with that of an optimal… …   Wikipedia

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Vertex cover — In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical… …   Wikipedia

  • Maximum coverage problem — The maximum coverage problem is a classical question in computer science and computational complexity theory. It is a problem that is widely taught in approximation algorithms. As input you are given several sets and a number k. The sets may have …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”