Domination Analysis¶
Domination analysis evaluates a heuristic by the number of feasible solutions its output is guaranteed to match or beat, rather than only by its gap from the optimum.
Core Idea¶
Domination analysis asks where an algorithm's output ranks among all feasible solutions of the same optimization instance. For minimization, a returned solution dominates a solution of equal or greater cost. Its instance-level domination count includes the output itself. The algorithmic domination number d(n) is the largest lower bound on that count that holds for every size-n instance—not a count observed on a convenient test case. Dividing by the number of feasible solutions yields a worst-case domination ratio, provided the denominator counts the right solution space.[1]
This differs from a conventional approximation bound, which compares an output's objective value to the optimum. A tour can outrank many tours yet be far from the best tour if the cost distribution is sparse near the optimum. Conversely, a good absolute cost gap does not state how many alternatives it outranks. The original TSP literature used this ordinal lens to prove both negative and positive heuristic results.[1][2]
Structural Signature¶
Sig role-phrases:
- Feasible solution set: all solutions to one instance, counted without double-counting equivalent representations.
- Objective ordering: “no worse” is defined by minimizing cost or maximizing value; ties count.
- Heuristic output: the particular feasible solution whose rank is measured.
- Worst-instance quantifier: a guarantee that the output outranks at least
d(n)solutions on every size-ninput. - Normalization and comparison:
d(n)divided by the feasible-space size, with optimum-value approximation kept separate.[1][2]
For a fixed minimization instance I, write D(A,I)=|{x in F(I): c(x)≥c(A(I))}|. Then d_A(n)=min_{|I|=n} D(A,I) for a deterministic algorithm and a specified instance family. This formulation makes the quantifier visible. A high D on one instance is not proof of a high d_A(n).
What It Is Not¶
Domination is not graph-theoretic vertex domination, where a dominating set covers neighboring vertices. The common word “domination” here refers to objective ordering of complete feasible solutions. It is also not a standard approximation ratio: a normalized rank near one says the output beats almost all feasible solutions, not that its cost is almost optimal. A purely experimental percentile from sampled tours may estimate an instance property but is not a theorem for every instance.[1]
The denominator matters. For a complete directed traveling-salesman problem (ATSP) with n vertices and a fixed start, there are (n−1)! distinct directed tours. For the undirected symmetric version (STSP), reversal identifies pairs, giving (n−1)!/2 tours when n>2. Using the directed count as the symmetric denominator silently halves the ratio. A quadratic-assignment problem uses permutations of assignments rather than TSP tours, so its feasible count and proof obligations must be established separately.[1][3]
Scope of Application¶
Original work by Gutin, Yeo and Zverovich defines the TSP domination number and proves a severe boundary for simple tour construction: for every applicable n, there exists a general ATSP or STSP instance on which greedy returns a worst tour. This is a worst-case construction, not a statement that greedy is normally worst on Euclidean data. It means a favorable average empirical reputation cannot by itself provide a nontrivial universal domination guarantee for the unrestricted problem class.[1]
Punnen and Kabadi give a contrasting original ATSP patching algorithm with domination number at least (n−2)!. Against (n−1)! directed tours, that lower bound normalizes to at least 1/(n−1) on the theorem's instance family. This remains a rank guarantee, not an objective-value approximation bound. Separate Gutin–Yeo work asks an analogous factorial-domination question for quadratic assignment; its publisher abstract does not justify importing the TSP denominator or a particular QAP numerical ratio into this entry.[2][3]
Clarity¶
Suppose a minimization instance has four feasible costs 0, 1, 2, 3 and a heuristic returns the solution costing 1. It is no worse than the solutions costing 1, 2, 3, so its count is three and its instance ratio is 3/4. Now replace the costs by 0, 100, 101, 102 and let the heuristic return cost 100. Its rank stays 3/4 although its gap from optimum changes from one to one hundred. These are author-constructed lists illustrating the definition, not published algorithm examples. They show why ordinal coverage cannot be read as closeness in cost.[1]
For ATSP, choosing a start vertex removes cyclic rotations of the same directed route, leaving (n−1)! ordered tours. In STSP, a route and its reverse describe the same undirected tour, so the count halves for nondegenerate n. An assertion such as “the algorithm beats (n−2)! tours” becomes a meaningful ratio only after specifying which space is being counted.[1][2]
Manages Complexity¶
The method replaces a hard-to-interpret raw cost on one instance with a guaranteed ordinal position. It can separate algorithms for which ordinary approximation bounds are weak or unavailable: one construction shows greedy can land at the very bottom; another proves patching cannot land below a factorial-sized block of alternatives. The relevant theorem controls all instances of the stated size and problem family, not merely a benchmark sample.[1][2]
At the same time, counting all feasible solutions is combinatorially enormous and the guarantee need not make it practical to enumerate the rank on an arbitrary instance. The theory proves bounds through structural arguments about tours. It does not render cost magnitude irrelevant. A decision-maker may still need the absolute or relative cost gap; rank coverage and value quality answer different questions.[1][2]
Abstract Reasoning¶
First state the problem's finite feasible set F(I), objective direction and equivalence rule. Given output A(I), count solutions x satisfying c(x)≥c(A(I)) for minimization (reverse for maximization). Include ties and the output itself. The denominator |F(I)| yields an instance ratio; a theorem about d_A(n) must then take the minimum over all permitted size-n instances. This prevents the common slide from “beat many tours here” to “guaranteed to beat many everywhere.”[1]
The greedy-worst construction is a counterexample generator: a single admissible bad instance at each n defeats any proposed larger universal lower bound for that heuristic. The patching result is a lower-bound proof: all admissible instances meet (n−2)!, so its normalized directed-tour guarantee is at least 1/(n−1). The two theorems have opposite quantifier force. Neither alone compares the heuristics' runtimes, practical average performance or approximation ratios to the optimal tour.[1][2]
Knowledge Transfer¶
The ranking skeleton transfers from TSP to other finite combinatorial problems, including quadratic assignment, only after rebuilding the feasible set and objective order. Gutin and Yeo considered a factorial-domination question for QAP, while later work used domination ratios to distinguish DOM-easy and DOM-hard optimization classes. These papers support transfer of the analysis question, not transfer of (n−1)! tour counting or a TSP algorithm to assignment problems.[3][4]
The contrast with the live Approximation Algorithm entry is instructive. That entry's current one-liner requires a worst-case quality bound relative to the optimum. Domination analysis can furnish a worst-case rank bound without that value guarantee. It is therefore a verified contrastive catalog neighbor, not a strict parent. Whether a specific algorithm has both sorts of guarantee is a separate theorem.
Examples¶
Greedy tour construction can be worst¶
Gutin, Yeo and Zverovich proved that, for every size in the theorem's range, there is a general asymmetric or symmetric TSP instance on which greedy tour construction finds a worst tour. Their article explicitly contrasts this worst-case fact with acceptable empirical behavior on Euclidean TSP instances. The mathematical result limits a universal rank claim: a heuristic that can return a bottom-ranked tour cannot be assigned a nontrivial guaranteed domination number solely because it performs well in a restricted experimental setting.[1]
Mapped back: all Hamilton tours of the constructed instance are the feasible solution set; tour length provides the objective ordering; greedy's produced tour is the heuristic output; the construction for each n attacks the worst-instance quantifier; using the correct directed or undirected tour count is the normalization and comparison. “Worst” does not require an assertion about the algorithm's average behavior or a made-up instance edge-cost matrix.
Patching algorithm's positive factorial guarantee¶
Punnen and Kabadi's original ATSP paper reports a patching algorithm whose returned tour has domination number at least (n−2)!. With (n−1)! directed tours, the guaranteed fraction is at least 1/(n−1). The factorial count can be large in absolute terms even though the normalized fraction declines with n; both views are needed to interpret it. The publisher abstract supplies the bound, but this entry does not claim to reproduce the paper's proof or a particular run of the algorithm.[2][1]
Mapped back: directed tours are the feasible solution set; their costs give the objective ordering; the patching result concerns its heuristic output; “at least (n−2)! for every admitted instance” is the worst-instance quantifier; division by (n−1)! gives the normalization and comparison. It cannot be relabeled a guarantee that tour cost is within 1/(n−1) of optimum.
Structural Tensions¶
Rank coverage versus cost-gap information. Domination analysis gains an order-based coverage statistic: it reports the share of feasible solutions no better than the output and remains unchanged when costs are transformed without changing their order. Its cost is that it discards distance to the optimum. Approximation analysis retains value closeness but does not say how common worse solutions are. The two four-cost lists in Clarity have identical rank 3/4 yet optimum gaps of one and one hundred; choosing only the rank hides a consequential magnitude difference. Conversely, a stated gap without a distribution of other costs cannot determine rank. This is a genuine information tradeoff between metrics, not a claim that one algorithm must be slow or inaccurate. Diagnostic: are we trying to certify prevalence of worse alternatives, closeness to the best value, or both?[1]
Structural–Framed Character¶
Domination analysis is near the formal structural end: feasible sets, objective order, quantifiers and counts are mathematical. The evaluative choice to prefer rank coverage to value gap is nevertheless human, and a heuristic's use depends on decision context. Its institutional origin lies in combinatorial optimization and approximation-algorithm theory, not in graph-theoretic domination despite shared vocabulary. The word “dominates” travels to QAP and other finite optimization only when the no-worse ordering and complete feasible space can be identified. Importing ATSP tour counts or a good one-instance percentile into a QAP theorem is false recognition. Its character: a formal worst-case ordinal performance lens whose practical weight depends on what quality question the user needs answered.[1][3]
Structural Core vs. Domain Accent¶
The skeletal relation is finite feasible set → objective ordering → output's no-worse count → minimum across instances → normalized rank guarantee. TSP tours and QAP permutations are domain accents, but the mechanism still requires computational optimization, feasible-solution counting and a size-indexed algorithm. The named entry fails the prime bar because “dominance” without these commitments could mean graph coverage, Pareto dominance or ordinary control. Its live strict genus is Evaluation; a separate portable rank-guarantee prime would require independently worked unlike domains and precise non-equivalence to value approximation.
Instantiates / Related Primes¶
This entry is a kind of Evaluation.
Strict parent: Evaluation. Domination analysis assigns a worst-case rank measure to algorithm outputs; many evaluations do not count dominated feasible solutions. Approximation Algorithm remains a contrastive neighbor: its worst-case guarantee is relative to optimum, whereas domination may certify only rank.
Relationships to Other Abstractions¶
Current abstraction Domination Analysis Domain-specific
Parents (1) — more general patterns this builds on
-
Domination Analysis is a kind of Evaluation Prime
Domination analysis evaluates an output by guaranteed feasible-solution rank.It assigns a worst-case ordinal quality measure to algorithm output; Evaluation also covers methods without this rank/count criterion.
Hierarchy path (1) — routes to 1 parentless root
- Domination Analysis → Evaluation → Comparison → Self Checking
Neighborhood in Abstraction Space¶
Domination Analysis sits in a sparse region of the domain-specific corpus (80th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Combinatorial Optimization & Game Problems (12 abstractions)
Nearest neighbors
- NP-Equivalent — 0.83
- Maximum Inner-Product Search — 0.82
- L-Reduction — 0.82
- Matroid-Constrained Number Partitioning — 0.82
- Portfolio Optimization — 0.82
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Do not confuse algorithmic domination number with a favorable observed instance count, or directed-tour (n−1)! with undirected-tour (n−1)!/2. “Worst tour” is a worst-case construction, not the typical Euclidean performance of greedy. The (n−2)! patching result is a rank bound, not a tour-cost approximation factor. Graph domination sets, Pareto dominance among multiple objectives and empirical random-tour percentiles are distinct identities unless specifically reformulated into this finite-set objective ordering.[1][2]
References¶
[1] Gutin, Gregory, Anders Yeo, and Alexey Zverovich. “Traveling Salesman Should Not Be Greedy: Domination Analysis of Greedy-Type Heuristics for the TSP.” Discrete Applied Mathematics 117 (2002), 81–86. Original publisher text and abstract: https://www.sciencedirect.com/science/article/pii/S0166218X01001950 . First-party author-institution full-text route: https://pure.royalholloway.ac.uk/files/878402/gutin-traveling_salesman_should_not_be_greedy.pdf . DOI 10.1016/S0166-218X(01)00195-0. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q
[2] Punnen, Abraham P., and Santosh N. Kabadi. “Domination Analysis of Some Heuristics for the Traveling Salesman Problem.” Discrete Applied Mathematics 119 (2002), 117–128. Original publisher abstract (full proof not inspected): https://www.sciencedirect.com/science/article/pii/S0166218X01002682 . DOI 10.1016/S0166-218X(01)00268-2. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i
[3] Gutin, Gregory, and Anders Yeo. “Polynomial Approximation Algorithms for the TSP and the QAP with a Factorial Domination Number.” Discrete Applied Mathematics 119 (2002), 107–116. Original publisher abstract: https://www.sciencedirect.com/science/article/pii/S0166218X01002670 . DOI 10.1016/S0166-218X(01)00267-0. registry ↩a ↩b ↩c ↩d
[4] Gutin, Gregory, and Anders Yeo. “Domination Analysis of Combinatorial Optimization Problems.” Discrete Applied Mathematics 129 (2003), 513–520. Original publisher abstract: https://www.sciencedirect.com/science/article/pii/S0166218X03003597 . DOI 10.1016/S0166-218X(03)00359-7. registry ↩