Domination analysis of an

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

is a way to estimate its performance, introduced by Glover and Punnen in 1997. Unlike the classical

approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...

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 ,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 The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

, 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 In statistics, quality assurance, and survey methodology, sampling is the selection of a subset (a statistical sample) of individuals from within a statistical population to estimate characteristics of the whole population. Statisticians attem ...

s of a problem's solution space, as it is in the Traveling salesman problem, then it is straightforward for a

randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performa ...

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 In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The 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.

Known Results

This section contains a technical survey of known results.

Vertex Cover

Inapproximability. Let ε > 0. Unless

P=NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...

, there is no polynomial algorithm for Vertex Cover 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^ε).

Max Satisfiability

TSP

References

* * * {{cite web , author = Orlin, James B. and Sharma, Dushyant , title = The Extended Neighborhood: Definition and Characterization , year = 2002 , url = http://web.mit.edu/sloan-msa/Papers/3.4.pdf Approximation algorithms