Worst case analysis of Max-Regret, Greedy and other heuristics for Multidimensional Assignment and Traveling Salesman Problems
Tóm tắt
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.
Tài liệu tham khảo
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)
Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Oper. Res. 39, 150–161 (1991)
Bendall, G., Margot, F.: Greedy type resistance of combinatorial problems. Discret. Optim. 3, 288–298 (2006)
Berend, D., Skiena, S., Twitto, Y.: Combinatorial dominance guarantees for problems with infeasible solutions (2007, submitted).
Burkard, R., Cela, E.: Linear assignment problems and extensions. In: Du, Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 75–149. Kluwer Academic, Dordrecht (1999)
Ghosh, D., Goldengorin, B., Gutin, G., Jäger, G.: Tolerance-based greedy algorithms for the traveling salesman problem. Communic. DQM 10, 52–70 (2007)
Glover, F., Punnen, A.: The traveling salesman problem: new solvable cases and linkages with the development of approximation algorithms. J. Oper. Res. Soc. 48, 502–510 (1997)
Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Construction heuristics for the asymmetric TSP. Eur. J. Oper. Res. 129, 555–568 (2001)
Goldengorin, B., Jäger, G., Molitor, P.: Tolerances applied in combinatorial optimization. J. Comput. Sci. 2(9), 716–734 (2006)
Gupta, P., Kahng, A.B., Mantik, S.: Routing-aware scan chain ordering. ACM Trans. Des. Autom. Electron. Syst. 10(3), 546–560 (2005)
Gutin, G., Punnen, A.: The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)
Gutin, G., Yeo, A.: Domination analysis of combinatorial optimization algorithms and problems. In: Golumbic, M., Hartman, I. (eds.) Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications. Springer, Berlin (2005)
Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discret. Appl. Math. 119, 107–116 (2002)
Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126, 106–130 (2000)
Johnson, D.S., Gutin, G., McGeoch, L., Yeo, A., Zhang, X., Zverovitch, A.: Experimental analysis of heuristics for ATSP. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)
Koller, A.E., Noble, S.D.: Domination analysis of greedy heuristics for the frequency assignment problem. Discret. Math. 275, 331–338 (2004)
Murphey, R., Pardalos, P.M., Pitsoulis, L.S.: A parallel GRASP for the data association multidimensional assignment problem. In: Parallel Processing of Discrete Problems. The IMA Volumes in Mathematics and its Applications, vol. 106, pp. 159–180 (1998)
Pierskalla, W.P.: The multidimensional assignment problem. Oper. Res. 16, 422–431 (1968)
Poore, A.B.: Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput. Optim. Appl. 3, 27–54 (1994)
Punnen, A.P.: The traveling salesman problem: applications, formulations and variations. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)
Punnen, A.P., Kabadi, S.: Domination analysis of some heuristics for the traveling salesman problem. Discret. Appl. Math. 119, 117–128 (2002)
Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica 35, 111–127 (2003)
Pusztaszeri, J., Rensing, P.E., Liebling, T.M.: Tracking elementary particles near their primary vertex: a combinatorial approach. J. Glob. Optim. 16, 422–431 (1995)
Reinfeld, N.V., Vogel, W.R.: Mathematical Programming. Prentice-Hall, Englewood Cliffs (1958)
Robertson, A.J.: A set of greedy randomized adaptive local search procedure implementations for the multidimensional assignment problem. Comput. Optim. Appl. 19, 145–164 (2001)
Xu, L., Tan, A.C., Naiman, D.Q., Geman, D., Winslow, R.L.: Robust prostate cancer marker genes emerge from direct integration of inter-study microarray data. Bioinformatics 21, 3905–3911 (2005)