{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:36:37Z","timestamp":1742913397602,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":33,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_136","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:05:19Z","timestamp":1219662319000},"page":"792-802","source":"Crossref","is-referenced-by-count":0,"title":["Domination Analysis in Combinatorial Optimization"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"136_CR1_136","doi-asserted-by":"crossref","unstructured":"Ahuja RK, Ergun \u00d6, Orlin JB, Punnen AP (2002) A\u00a0survey of very large-scale neighborhood search\ntechniques. Discret Appl Math 123:75\u2013102","DOI":"10.1016\/S0166-218X(01)00338-9"},{"key":"136_CR2_136","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 (2004) Algorithms with large domination ratio. J\u00a0Algorithms 50:118\u2013131","journal-title":"J Algorithms"},{"key":"136_CR3_136","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,\nKann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and Approximation. Springer, Berlin"},{"key":"136_CR4_136","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 MJ (1991) An algorithm for the three-index\nassignment problem. Oper Res 39:150\u2013161","journal-title":"Oper Res"},{"key":"136_CR5_136","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2000","unstructured":"Bang-Jensen J, Gutin G (2000) Digraphs:\nTheory, Algorithms and Applications. Springer, London"},{"key":"136_CR6_136","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 (2004) When the greedy algorithm\nfails. Discret Optim 1:121\u2013127","journal-title":"Discret Optim"},{"key":"136_CR7_136","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 (2003) Transformations of Generalized ATSP into ATSP:\nexperimental and theoretical study. Oper Res Lett 31:357\u2013365","journal-title":"Oper Res Lett"},{"key":"136_CR8_136","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.disopt.2006.03.001","volume":"3","author":"G Bendall","year":"2006","unstructured":"Bendall G, Margot F (2006) Greedy Type Resistance of\nCombinatorial Problems. Discret Optim 3:288\u2013298","journal-title":"Discret Optim"},{"key":"136_CR9_136","volume-title":"The Theory of Graphs","author":"C Berge","year":"1958","unstructured":"Berge C (1958) The Theory of Graphs. Methuen, London"},{"key":"136_CR10_136","unstructured":"Berend\nB, Skiena SS, Twitto Y, Combinatorial\ndominance guarantees for heuristic algorithms. ACM Trans Algorithm (to appear)"},{"key":"136_CR11_136","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornuejols","year":"1977","unstructured":"Cornuejols G, Fisher ML, Nemhauser GL (1977) Location of bank accounts to optimize float; an\nanalytic study of exact and approximate algorithms. Manag Sci 23:789\u2013810","journal-title":"Manag Sci"},{"key":"136_CR12_136","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"VG Deineko","year":"2000","unstructured":"Deineko VG, Woeginger GJ (2000) A\u00a0study of exponential\nneighbourhoods for the traveling salesman problem and the quadratic\nassignment problem. Math Prog Ser A 87:519\u2013542","journal-title":"Math Prog Ser A"},{"key":"136_CR13_136","first-page":"521","volume":"41","author":"D Ghosh","year":"2007","unstructured":"Ghosh D, Goldengorin B, Gutin G, J\u00e4ger G (2007) Tolerance\u2010based greedy algorithms for the traveling\nsalesman problem. Commun DQM 41:521\u2013538","journal-title":"Commun DQM"},{"key":"136_CR14_136","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 (2001) Construction heuristics for the asymmetric\nTSP. Eur J Oper Res 129:555\u2013568","journal-title":"Eur J Oper Res"},{"key":"136_CR15_136","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/11970125_17","volume":"4368","author":"G Gutin","year":"2006","unstructured":"Gutin G, Goldengorin B, Huang J (2006) Worst Case Analysis of\nMax-Regret, Greedy and Other Heuristics for Multidimensional\nAssignment and Traveling Salesman Problems. Lect Notes\nComput Sci 4368:214\u2013225","journal-title":"Lect Notes Comput Sci"},{"key":"136_CR16_136","doi-asserted-by":"publisher","first-page":"2613","DOI":"10.1016\/j.dam.2006.02.010","volume":"154","author":"G Gutin","year":"2006","unstructured":"Gutin G, Jensen T, Yeo A (2006) Domination analysis for\nminimum multiprocessor scheduling. Discret Appl Math 154:2613\u20132619","journal-title":"Discret Appl Math"},{"key":"136_CR17_136","first-page":"52","volume":"1","author":"G Gutin","year":"2006","unstructured":"Gutin\nG, Koller A, Yeo A (2006) Note on Upper Bounds for TSP\nDomination Number. Algorithm Oper Res 1:52\u201354","journal-title":"Algorithm Oper Res"},{"key":"136_CR18_136","unstructured":"Gutin G, Vainshtein A, Yeo A (2002) When greedy-type algorithms\nfail. Unpublished manuscript"},{"key":"136_CR19_136","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/S0166-218X(03)00359-7","volume":"129","author":"G Gutin","year":"2003","unstructured":"Gutin G, Vainshtein A, Yeo A (2003) Domination Analysis of Combinatorial Optimization Problems. Discret Appl Math 129:513\u2013520","journal-title":"Discret Appl Math"},{"key":"136_CR20_136","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G Gutin","year":"2002","unstructured":"Gutin\nG, Yeo A (2002) Polynomial approximation\nalgorithms for the TSP and the QAP with a\u00a0factorial domination\nnumber. Discret Appl Math 119:107\u2013116","journal-title":"Discret Appl Math"},{"key":"136_CR21_136","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 (2002) Anti-matroids. Oper Res Lett 30:97\u201399","journal-title":"Oper Res Lett"},{"key":"136_CR22_136","first-page":"152","volume-title":"Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications","author":"G Gutin","year":"2005","unstructured":"Gutin G, Yeo A (2005) Domination Analysis of Combinatorial\nOptimization Algorithms and Problems. In: Golumbic M, Hartman I\n(eds) Graph Theory, Combinatorics and Algorithms:\nInterdisciplinary Applications. Springer, New York, pp 152\u2013176"},{"key":"136_CR23_136","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0166-218X(01)00195-0","volume":"117","author":"G Gutin","year":"2002","unstructured":"Gutin G, Yeo A, Zverovitch A (2002) Traveling salesman should not be greedy: domination analysis of\ngreedy-type heuristics for the TSP. Discret Appl Math 117:81\u201386","journal-title":"Discret Appl Math"},{"key":"136_CR24_136","first-page":"223","volume-title":"The Traveling Salesman Problem and its Variations","author":"G Gutin","year":"2002","unstructured":"Gutin G, Yeo A, Zverovitch A (2002) Exponential Neighborhoods and Domination Analysis\nfor the TSP. In: Gutin G, Punnen AP (eds) The Traveling Salesman Problem and its Variations. Kluwer,\nDordrecht, pp 223\u2013256"},{"key":"136_CR25_136","first-page":"445","volume-title":"The Traveling Salesman Problem and its Variations","author":"DS Johnson","year":"2002","unstructured":"Johnson DS, Gutin G, McGeoch LA, Yeo A, Zhang X, Zverovitch A (2002) Experimental Analysis of Heuristics for ATSP. In: Gutin G, Punnen AP (eds) The Traveling Salesman Problem and its\nVariations. Kluwer, Dordrecht, pp 445\u2013487"},{"key":"136_CR26_136","first-page":"251","volume-title":"Local Search in Combinatorial Optimization","author":"DS Johnson","year":"1997","unstructured":"Johnson DS, McGeoch LA (1997) The traveling salesman problem: A\u00a0case study in local\noptimization. In: Aarts EHL, Lenstra JK (eds) Local\nSearch in Combinatorial Optimization. Wiley, Chichester, pp 251\u2013310"},{"key":"136_CR27_136","first-page":"369","volume-title":"The Traveling Salesman Problem and its Variations","author":"DS Johnson","year":"2002","unstructured":"Johnson DS, McGeoch LA (2002) Experimental Analysis of Heuristics for STSP. In: Gutin G,\nPunnen AP (eds) The Traveling Salesman Problem and its Variations. Kluwer,\n\t  Dordrecht, pp 369\u2013443"},{"key":"136_CR28_136","first-page":"205","volume":"22","author":"H Kise","year":"1979","unstructured":"Kise\nH, Ibaraki T, Mine H (1979) Performance analysis of six approximation\nalgorithms for the one-machine maximum lateness scheduling problem with ready times. J\u00a0Oper Res Soc\nJapan 22:205\u2013223","journal-title":"J Oper Res Soc Japan"},{"key":"136_CR29_136","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"AP Punnen","year":"2003","unstructured":"Punnen AP, Margot F, Kabadi SN (2003) TSP heuristics: domination analysis and\ncomplexity. Algorithmica 35:111\u2013127","journal-title":"Algorithmica"},{"key":"136_CR30_136","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1023\/A:1011285402433","volume":"19","author":"AJ Robertson","year":"2001","unstructured":"Robertson AJ (2001) A\u00a0set of greedy randomized adaptive local search procedure\nimplementations for the multidimentional assignment problem. Comput Optim Appl 19:145\u2013164","journal-title":"Comput Optim Appl"},{"key":"136_CR31_136","first-page":"18","volume":"4","author":"VI Rublineckii","year":"1973","unstructured":"Rublineckii VI (1973) Estimates of the accuracy of procedures in the Traveling Salesman\nProblem. Numer Math Comput Tech 4:18\u201323 (in Russian)","journal-title":"Numer Math Comput Tech"},{"key":"136_CR32_136","unstructured":"Sarvanov VI (1976) The mean value of the functional of the assignment problem. Vestsi\nAkad Navuk BSSR, Ser Fiz-Mat Navuk 2:111\u2013114 (in Russian)"},{"key":"136_CR33_136","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E Zemel","year":"1981","unstructured":"Zemel E (1981) Measuring the quality of approximate solutions to zero-one programming\nproblems. Math Oper Res 6:319\u2013332","journal-title":"Math Oper Res"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T11:11:58Z","timestamp":1720696318000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_136","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}