Introduction to Domination Analysis

In the recently published book on the Traveling Salesman Problem, half of Chapter 6 is devoted to domination analysis (DA) of heuristics for the Traveling Salesman Problem. Another chapter (in preparation) is a detailed overview of the whole area of DA. Both chapters are of considerable length. The purpose of this paper is to give … Read more

Domination analysis for minimum multiprocessor scheduling

Let $P$ be a combinatorial optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,s)$ is the maximal real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $s$ is not worse than at least the fraction $q$ of the feasible solutions … Read more