{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T17:11:07Z","timestamp":1791997867156,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540695134","type":"print"},{"value":"9783540695141","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_17","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T05:47:40Z","timestamp":1169617660000},"page":"214-225","source":"Crossref","is-referenced-by-count":7,"title":["Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boris","family":"Goldengorin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N. Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms\u00a050, 118\u2013131 (2004)","journal-title":"J. Algorithms"},{"key":"17_CR2","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":"17_CR3","doi-asserted-by":"publisher","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. Operations Research\u00a039, 150\u2013161 (1991)","journal-title":"Operations Research"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.disopt.2004.03.007","volume":"1","author":"J. Bang-Jensen","year":"2004","unstructured":"Bang-Jensen, J., Gutin, G., Yeo, A.: When the greedy algorithm fails. Discrete Optimization\u00a01, 121\u2013127 (2004)","journal-title":"Discrete Optimization"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/11424925_43","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2005","author":"H. Bekker","year":"2005","unstructured":"Bekker, H., Braad, E.P., Goldengorin, B.: Using bipartite and multidimentional matchings to select roots of a system of polynomial equations. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Lagan\u00e1, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol.\u00a03483, pp. 397\u2013406. Springer, Heidelberg (2005)"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0167-6377(03)00031-2","volume":"31","author":"D. Ben-Arieh","year":"2003","unstructured":"Ben-Arieh, D., Gutin, G., Penn, M., Yeo, A., Zverovitch, A.: Transformations of generalized ATSP into ATSP. Operations Research Letters\u00a031, 357\u2013365 (2003)","journal-title":"Operations Research Letters"},{"key":"17_CR7","unstructured":"Bendall, G., Margot, F.: Greedy Type Resistance of Combinatorial Problems. To appear in Discrete Optimization"},{"key":"17_CR8","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 Publishers, Dordrecht (1999)"},{"key":"17_CR9","unstructured":"Ghosh, D., Goldengorin, B., Gutin, G., J\u00e4ger, G.: Tolerance based greedy algorithms for the traveling salesman problem. To appear in Communic. in DQM"},{"key":"17_CR10","doi-asserted-by":"publisher","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. European Journal of Operational Research\u00a0129, 555\u2013568 (2001)","journal-title":"European Journal of Operational Research"},{"key":"17_CR11","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.\u00a048, 502\u2013510 (1997)","journal-title":"J. Oper. Res. Soc."},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/11775096_19","volume-title":"Algorithmic Aspects in Information and Management","author":"B. Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Some Basics on Tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 194\u2013206. Springer, Heidelberg (2006)"},{"key":"17_CR13","volume-title":"The Traveling Salesman Problem and its Variations","year":"2002","unstructured":"Gutin, G., Punnen, A. (eds.): The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht (2002)"},{"key":"17_CR14","first-page":"13","volume":"8","author":"G. Gutin","year":"2005","unstructured":"Gutin, G., Jakubowicz, H., Ronnen, S., Zverovitch, A.: Seismic vessel problem. Communic. in DQM\u00a08, 13\u201320 (2005)","journal-title":"Communic. in DQM"},{"key":"17_CR15","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, Heidelberg (2005)"},{"key":"17_CR16","doi-asserted-by":"publisher","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 QAP with a factorial domination number. Discrete Appl. Math.\u00a0119, 107\u2013116 (2002)","journal-title":"Discrete Appl. Math."},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0167-6377(02)00117-7","volume":"30","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A.: Anti-matroids. Operations Research Letters\u00a030, 97\u201399 (2002)","journal-title":"Operations Research Letters"},{"key":"17_CR18","volume-title":"The Traveling Salesman Problem and its Variations","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A., Zverovitch, A.: Exponential Neighborhoods and Domination Analysis for the TSP. In: Gutin, G., Punnen, A. (eds.) The Traveling Salesman Problem and its Variations. Kluwer, Dordrecht (2002)"},{"key":"17_CR19","doi-asserted-by":"publisher","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. Europ. J. Oper. Res.\u00a0126, 106\u2013130 (2000)","journal-title":"Europ. J. Oper. Res."},{"key":"17_CR20","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, Dordrecht (2002)"},{"key":"17_CR21","doi-asserted-by":"publisher","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. Discrete Math.\u00a0275, 331\u2013338 (2004)","journal-title":"Discrete Math."},{"key":"17_CR22","doi-asserted-by":"publisher","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\u00a035, 111\u2013127 (2003)","journal-title":"Algorithmica"},{"key":"17_CR23","doi-asserted-by":"publisher","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. Discrete Appl. Math.\u00a0119, 117\u2013128 (2002)","journal-title":"Discrete Appl. Math."},{"key":"17_CR24","doi-asserted-by":"publisher","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 multidimentional assignment problem. Computational Optimization and Applications\u00a019, 145\u2013164 (2001)","journal-title":"Computational Optimization and Applications"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:23:49Z","timestamp":1619508229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11970125_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007]]}}}