• Calendar

November 21, Tuesday
12:00 – 14:00

Combinatorial optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio which reflects the quality of returned solution in the worst case. The domination number is a complement parameter indicating the > quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman finds the unique worst possible solution for some instances of the s-dimensional ($s \ge 3$) assignment problem (s-AP) and the asymmetric traveling salesman problems (ATSP) of each possible size. It was proved earlier that Greedy has the same property for ATSP and it's not difficult to show that Greedy has the same property for s-AP ($s \ge 2$). This means that the domination number of all above mentioned heuristics (for ATSP and s-AP) is 1. We show that the Triple Interchange heuristic (for $s = 3$) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for s-AP ($s \ge 3$). ATSP heuristics of factorial domination number will also be discussed