Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems

摘要

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting 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 (Oper. Res. 39:150-161, 1991) finds the unique worst possible solution for some instances of the s-dimensional (s >= 3) assignment and asymmetric traveling salesman problems of each possible size. 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 the s-dimensional (s >= 3) assignment problem.