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 evaluates the rank of a heuristic's output among all feasible solutions. For minimization, the output dominates solutions of equal or greater cost. An algorithm's domination number d(n) is a lower count guaranteed across every size-n instance, not a favorable count observed once. Divide by the correctly counted feasible space to obtain a domination ratio. This rank measure does not state closeness to the optimum.
Scope of Application¶
For directed TSP on n cities there are (n−1)! tours with a fixed start; for undirected symmetric TSP the nondegenerate count is half. Gutin, Yeo and Zverovich proved greedy construction can return a worst tour on a general TSP instance of each size in their theorem. Punnen and Kabadi's ATSP patching algorithm has a contrasting guarantee of at least (n−2)! dominated tours, a fraction at least 1/(n−1) of directed tours. Analogous rank questions exist for quadratic assignment, but its feasible count must be established separately.
Clarity¶
If four feasible costs are 0,1,2,3 and output cost is 1, it dominates three of four. If the costs are 0,100,101,102 and output cost is 100, it still dominates three of four, though the optimum gap rises from one to one hundred. This author-constructed arithmetic example shows rank is not a value approximation guarantee.
Manages Complexity¶
Rank guarantees expose a heuristic's worst-case standing even when cost-based approximation theorems are weak. They also need careful quantifiers: a bad construction refutes a universal lower bound, while a positive proof must cover all allowed instances. The sampled or average behavior of greedy on Euclidean TSP is not the same as its unrestricted worst-case guarantee.
Abstract Reasoning¶
Specify the feasible set, objective order and equivalence of representations. Count every solution no better than the output, including ties. Minimize that count over all size-n instances to get an algorithmic guarantee. Normalize only with the right denominator; directed and undirected tours differ. A rank bound and an optimum-value bound answer different questions.
Knowledge Transfer¶
The feasible-set/order/output/worst-case skeleton transfers to other finite optimization problems, but TSP tour counts and algorithms do not. It is a specialized Evaluation by feasible-solution rank. The live Approximation Algorithm entry remains a contrastive neighbor because its guarantee is about objective value relative to optimum; domination analysis need not provide that guarantee.
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.
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