Domination analysis
Encyclopedia
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 solution, domination analysis involves examining the rank of the calculated solution in the sorted order of all possible solutions. In this style of analysis, an algorithm is said to have dominance number or domination number K, if there exists a subset of K different solutions to the problem among which the algorithm's output is the best. Domination analysis can also be expressed using a domination ratio, which is the fraction of the solution space that is no better than the given solution; this number always lies within the interval [0,1], with larger numbers indicating better solutions. Domination analysis is most commonly applied to problems for which the total number of possible solutions is known and for which exact solution is difficult.
For instance, in the Traveling salesman problem, there are (n-1)! possible solutions for a problem instance with n cities. If an algorithm can be shown to have dominance number close to (n-1)!, or equivalently to have domination ratio close to 1, then it can be taken as preferable to an algorithm with lower dominance number.
If it is possible to efficiently find random sample
s of a problem's solution space, as it is in the Traveling salesman problem, then it is straightforward for a randomized algorithm
to find a solution that with high probability has high domination ratio: simply construct a set of samples and select the best solution from among them. (See, e.g., Orlin and Sharma.)
The dominance number described here should not be confused with the domination number of a graph, which refers to the number of vertices in the smallest dominating set
of the graph.
Recently, a growing number of articles in which domination analysis has been applied to assess the performance of heuristics has appeared. This kind of analysis may be seen as competing with the classical approximation ratio analysis tradition. The two measures may also be viewed as complementary.
such that its domination number is greater than 3^((n-n^ε)/3).
Knapsack
Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Knapsack
such that its domination number is greater than 2^(n-n^ε).
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 can ever be efficient polynomial time exact...
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 solution, domination analysis involves examining the rank of the calculated solution in the sorted order of all possible solutions. In this style of analysis, an algorithm is said to have dominance number or domination number K, if there exists a subset of K different solutions to the problem among which the algorithm's output is the best. Domination analysis can also be expressed using a domination ratio, which is the fraction of the solution space that is no better than the given solution; this number always lies within the interval [0,1], with larger numbers indicating better solutions. Domination analysis is most commonly applied to problems for which the total number of possible solutions is known and for which exact solution is difficult.
For instance, in the Traveling salesman problem, there are (n-1)! possible solutions for a problem instance with n cities. If an algorithm can be shown to have dominance number close to (n-1)!, or equivalently to have domination ratio close to 1, then it can be taken as preferable to an algorithm with lower dominance number.
If it is possible to efficiently find random sample
Random sample
In statistics, a sample is a subject chosen from a population for investigation; a random sample is one chosen by a method involving an unpredictable component...
s of a problem's solution space, as it is in the Traveling salesman problem, then it is straightforward for a randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
to find a solution that with high probability has high domination ratio: simply construct a set of samples and select the best solution from among them. (See, e.g., Orlin and Sharma.)
The dominance number described here should not be confused with the domination number of a graph, which refers to the number of vertices in the smallest dominating set
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
of the graph.
Recently, a growing number of articles in which domination analysis has been applied to assess the performance of heuristics has appeared. This kind of analysis may be seen as competing with the classical approximation ratio analysis tradition. The two measures may also be viewed as complementary.
Vertex Cover
Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Vertex Coversuch that its domination number is greater than 3^((n-n^ε)/3).
KnapsackKnapsack problemThe knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
Inapproximability. Let ε > 0. Unless P=NP, there is no polynomial algorithm for Knapsacksuch that its domination number is greater than 2^(n-n^ε).