{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:16:09Z","timestamp":1773814569998,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,8,9]],"date-time":"2007-08-09T00:00:00Z","timestamp":1186617600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s10732-007-9033-3","type":"journal-article","created":{"date-parts":[[2007,8,8]],"date-time":"2007-08-08T09:45:07Z","timestamp":1186566307000},"page":"169-181","source":"Crossref","is-referenced-by-count":13,"title":["Worst case analysis of Max-Regret, Greedy and\u00a0other\u00a0heuristics for Multidimensional Assignment and\u00a0Traveling Salesman Problems"],"prefix":"10.1007","volume":"14","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Goldengorin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,8,9]]},"reference":[{"key":"9033_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)"},{"key":"9033_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/opre.39.1.150","volume":"39","author":"E. Balas","year":"1991","unstructured":"Balas, E., Saltzman, M.J.: An algorithm for the three-index assignment problem. Oper. Res. 39, 150\u2013161 (1991)","journal-title":"Oper. Res."},{"key":"9033_CR3","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.disopt.2006.03.001","volume":"3","author":"G. Bendall","year":"2006","unstructured":"Bendall, G., Margot, F.: Greedy type resistance of combinatorial problems. Discret. Optim. 3, 288\u2013298 (2006)","journal-title":"Discret. Optim."},{"key":"9033_CR4","doi-asserted-by":"crossref","unstructured":"Berend, D., Skiena, S., Twitto, Y.: Combinatorial dominance guarantees for problems with infeasible solutions (2007, submitted).","DOI":"10.1145\/1435375.1435383"},{"key":"9033_CR5","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4757-3023-4_2","volume-title":"Handbook of Combinatorial Optimization","author":"R. Burkard","year":"1999","unstructured":"Burkard, R., Cela, E.: Linear assignment problems and extensions. In: Du, Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 75\u2013149. Kluwer Academic, Dordrecht (1999)"},{"key":"9033_CR6","first-page":"52","volume":"10","author":"D. Ghosh","year":"2007","unstructured":"Ghosh, D., Goldengorin, B., Gutin, G., J\u00e4ger, G.: Tolerance-based greedy algorithms for the traveling salesman problem. Communic. DQM 10, 52\u201370 (2007)","journal-title":"Communic. DQM"},{"key":"9033_CR7","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1057\/palgrave.jors.2600392","volume":"48","author":"F. Glover","year":"1997","unstructured":"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\u2013510 (1997)","journal-title":"J. Oper. Res. Soc."},{"key":"9033_CR8","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/S0377-2217(99)00468-3","volume":"129","author":"F. Glover","year":"2001","unstructured":"Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Construction heuristics for the asymmetric TSP. Eur. J. Oper. Res. 129, 555\u2013568 (2001)","journal-title":"Eur. J. Oper. Res."},{"issue":"9","key":"9033_CR9","doi-asserted-by":"crossref","first-page":"716","DOI":"10.3844\/jcssp.2006.716.734","volume":"2","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Tolerances applied in combinatorial optimization. J. Comput. Sci. 2(9), 716\u2013734 (2006)","journal-title":"J. Comput. Sci."},{"issue":"3","key":"9033_CR10","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1145\/1080334.1080339","volume":"10","author":"P. Gupta","year":"2005","unstructured":"Gupta, P., Kahng, A.B., Mantik, S.: Routing-aware scan chain ordering. ACM Trans. Des. Autom. Electron. Syst. 10(3), 546\u2013560 (2005)","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"9033_CR11","volume-title":"The Traveling Salesman Problem and its Variations","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Punnen, A.: The Traveling Salesman Problem and its Variations. Kluwer Academic, Dordrecht (2002)"},{"key":"9033_CR12","volume-title":"Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications","author":"G. Gutin","year":"2005","unstructured":"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)"},{"key":"9033_CR13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discret. Appl. Math. 119, 107\u2013116 (2002)","journal-title":"Discret. Appl. Math."},{"key":"9033_CR14","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K. Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126, 106\u2013130 (2000)","journal-title":"Eur. J. Oper. Res."},{"key":"9033_CR15","volume-title":"The Traveling Salesman Problem and its Variations","author":"D.S. Johnson","year":"2002","unstructured":"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)"},{"key":"9033_CR16","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.disc.2003.05.008","volume":"275","author":"A.E. Koller","year":"2004","unstructured":"Koller, A.E., Noble, S.D.: Domination analysis of greedy heuristics for the frequency assignment problem. Discret. Math. 275, 331\u2013338 (2004)","journal-title":"Discret. Math."},{"key":"9033_CR17","doi-asserted-by":"crossref","unstructured":"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\u2013180 (1998)","DOI":"10.1007\/978-1-4612-1492-2_7"},{"key":"9033_CR18","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1287\/opre.16.2.422","volume":"16","author":"W.P. Pierskalla","year":"1968","unstructured":"Pierskalla, W.P.: The multidimensional assignment problem. Oper. Res. 16, 422\u2013431 (1968)","journal-title":"Oper. Res."},{"key":"9033_CR19","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF01299390","volume":"3","author":"A.B. Poore","year":"1994","unstructured":"Poore, A.B.: Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput. Optim. Appl. 3, 27\u201354 (1994)","journal-title":"Comput. Optim. Appl."},{"key":"9033_CR20","volume-title":"The Traveling Salesman Problem and its Variations","author":"A.P. Punnen","year":"2002","unstructured":"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)"},{"key":"9033_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0166-218X(01)00268-2","volume":"119","author":"A.P. Punnen","year":"2002","unstructured":"Punnen, A.P., Kabadi, S.: Domination analysis of some heuristics for the traveling salesman problem. Discret. Appl. Math. 119, 117\u2013128 (2002)","journal-title":"Discret. Appl. Math."},{"key":"9033_CR22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"A.P. Punnen","year":"2003","unstructured":"Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica 35, 111\u2013127 (2003)","journal-title":"Algorithmica"},{"key":"9033_CR23","first-page":"422","volume":"16","author":"J. Pusztaszeri","year":"1995","unstructured":"Pusztaszeri, J., Rensing, P.E., Liebling, T.M.: Tracking elementary particles near their primary vertex: a combinatorial approach. J. Glob. Optim. 16, 422\u2013431 (1995)","journal-title":"J. Glob. Optim."},{"key":"9033_CR24","volume-title":"Mathematical Programming","author":"N.V. Reinfeld","year":"1958","unstructured":"Reinfeld, N.V., Vogel, W.R.: Mathematical Programming. Prentice-Hall, Englewood Cliffs (1958)"},{"key":"9033_CR25","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1023\/A:1011285402433","volume":"19","author":"A.J. Robertson","year":"2001","unstructured":"Robertson, A.J.: A set of greedy randomized adaptive local search procedure implementations for the multidimensional assignment problem. Comput. Optim. Appl. 19, 145\u2013164 (2001)","journal-title":"Comput. Optim. Appl."},{"key":"9033_CR26","doi-asserted-by":"crossref","first-page":"3905","DOI":"10.1093\/bioinformatics\/bti647","volume":"21","author":"L. Xu","year":"2005","unstructured":"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\u20133911 (2005)","journal-title":"Bioinformatics"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-007-9033-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-007-9033-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-007-9033-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T18:54:28Z","timestamp":1559242468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-007-9033-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,9]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["9033"],"URL":"https:\/\/doi.org\/10.1007\/s10732-007-9033-3","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,9]]}}}