{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:30:07Z","timestamp":1759847407285},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,12,11]],"date-time":"2008-12-11T00:00:00Z","timestamp":1228953600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Memetic Comp."],"published-print":{"date-parts":[[2009,3]]},"DOI":"10.1007\/s12293-008-0001-8","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T05:06:14Z","timestamp":1228885574000},"page":"25-34","source":"Crossref","is-referenced-by-count":15,"title":["A selection of useful theoretical tools for the design and analysis of optimization heuristics"],"prefix":"10.1007","volume":"1","author":[{"given":"G.","family":"Gutin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Karapetyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,12,11]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"RK Ahuja","year":"2002","unstructured":"Ahuja RK, Ergun \u00d6, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discrete Appl Math 123: 75\u2013102","journal-title":"Discrete Appl Math"},{"key":"1_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N Alon","year":"2000","unstructured":"Alon N, Spencer J (2000) The probabilistic method, 2nd edn. Wiley, London","edition":"2"},{"key":"1_CR3","doi-asserted-by":"crossref","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 fails. Discrete Optim 1: 121\u2013127","journal-title":"Discrete Optim"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/0167-6377(82)90038-4","volume":"1","author":"JJ Bartholdi","year":"1982","unstructured":"Bartholdi JJ (1982) A good submatrix is hard to find. Oper Res Lett 1: 190\u2013193","journal-title":"Oper Res Lett"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","volume":"55","author":"J Beardwood","year":"1959","unstructured":"Beardwood J, Halton JH, Hammersley JM (1959) The shortest path through many points. Proc Camb Philo Soc 55: 299\u2013327","journal-title":"Proc Camb Philo Soc"},{"key":"1_CR6","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 (2006) Greedy type resistance of combinatorial problems. Discrete Optim 3: 288\u2013298","journal-title":"Discrete Optim"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/opre.50.1.3.17780","volume":"50","author":"RE Bixby","year":"2002","unstructured":"Bixby RE (2002) Solving real-world linear programs: A decade and more of progress. Oper Res 50: 3\u201315","journal-title":"Oper Res"},{"key":"1_CR8","unstructured":"Bodlaender HL, Downey RG, Fellows MR, Hermelin D (2007) On problems without polynomial kernels. In: Technical report UU-CS-2007-046, Utrecht University, The Netherlands"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Bollobas B (2001) Random Graphs. Cambridge University Press","DOI":"10.1017\/CBO9780511814068"},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s00291-006-0052-5","volume":"29","author":"T Brueggemann","year":"2007","unstructured":"Brueggemann T, Hurink J (2007) Two very large-scale neighborhoods for single machine scheduling. OR Spect 29: 513\u2013533","journal-title":"OR Spect"},{"key":"1_CR11","unstructured":"Chen J, Kanj IA, Xia G (2005) Simplicity is beauty: Improved upper bounds for vertex cover. In: Technical report TR05-008, DePaul University, Chicago"},{"key":"1_CR12","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/s101070050010","volume":"87","author":"VG Deineko","year":"2000","unstructured":"Deineko VG, Woeginger GJ (2000) A study of exponential neighbourhoods for the traveling salesman problem and the quadratic assignment problem. Math Prog Ser A 87: 519\u2013542","journal-title":"Math Prog Ser A"},{"key":"1_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey RG, Fellows MR (1999) Parameterized complexity. Springer, New York"},{"issue":"1","key":"1_CR14","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0305-0548(86)90062-6","volume":"13","author":"M Dror","year":"1986","unstructured":"Dror M, Levy L (1986) A vehicle routing improvement algorithm comparison of a \u201cgreedy\u201d and a matching implementation for inventory routing. Comput Oper Res 13(1): 33\u201345","journal-title":"Comput Oper Res"},{"issue":"1\u20132","key":"1_CR15","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10732-006-5561-5","volume":"12","author":"\u00d6 Ergun","year":"2006","unstructured":"Ergun \u00d6, Orlin JB, Steele-Feldman A (2006) Creating very large scale neighborhoods out of smaller ones by compounding moves. J Heuristics 12(1\u20132): 115\u2013140","journal-title":"J Heuristics"},{"key":"1_CR16","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Heidelberg"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"Fourer R, Gay DM (1994) Experience with a primal presolve algorithm. In: Large scale optimization: state of the art. Kluwer, Dordrecht, pp 135\u2013154","DOI":"10.1007\/978-1-4613-3632-7_8"},{"issue":"2\u20133","key":"1_CR18","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/s10107-005-0662-8","volume":"105","author":"R De Franceschi","year":"2006","unstructured":"De Franceschi R, Fischetti M, Toth P (2006) A new ilp-based refinement heuristic for vehicle routing problems. Math Program 105(2\u20133): 471\u2013499","journal-title":"Math Program"},{"key":"1_CR19","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. In: Series of books in the mathematical sciences. Freeman WH, San Francisco (January)"},{"key":"1_CR20","first-page":"52","volume":"10","author":"D Ghosh","year":"2007","unstructured":"Ghosh D, Goldengorin B, Gutin G, J\u00e4ger G (2007) Tolerance-based greedy algorithms for the traveling salesman problem. Commun DQM 10: 52\u201370","journal-title":"Commun DQM"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Grigni M, Koutsoupias E, Papadimitriou C (1995) An approximation scheme for planar graph tsp. In: Proceedings of the 36th annual symposium on foundations of computer science (FOCS\u201995), IEEE Computer Society, Washington, pp 640\u2013645","DOI":"10.1109\/SFCS.1995.492665"},{"issue":"3","key":"1_CR22","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1023\/B:JOTA.0000042592.16418.1b","volume":"122","author":"D Grundel","year":"2004","unstructured":"Grundel D, Oliveira C, Pardalos P (2004) Asymptotic properties of random multidimensional assignment problems. J Optim Theory Appl 122(3): 33\u201346","journal-title":"J Optim Theory Appl"},{"key":"1_CR23","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0166-218X(03)00361-5","volume":"137","author":"N Gulpinar","year":"2004","unstructured":"Gulpinar N, Gutin G, Mitra G, Zverovitch A (2004) Extracting pure network submatrices in linear programs using signed graphs. Discrete Appl Math 137: 359\u2013372","journal-title":"Discrete Appl Math"},{"issue":"1","key":"1_CR24","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. SIGACT News 38(1): 31\u201345","journal-title":"SIGACT News"},{"key":"1_CR25","unstructured":"Gutin G (1984) On an approach to solving the traveling salesman problem. In: Proceedings of the USSR conference on system research, Nauka, Moscow, pp 184\u2013185 (in Russian)"},{"issue":"2","key":"1_CR26","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s10732-007-9033-3","volume":"14","author":"G Gutin","year":"2008","unstructured":"Gutin G, Goldengorin B, Huang J (2008) Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems. J Heuristics 14(2): 169\u2013181","journal-title":"J Heuristics"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Gutin G, Karapetyan D (2008) Advances in greedy algorithms. In: Greedy like algorithms for the traveling salesman and multidimensional assignment problems, INTECH, in press","DOI":"10.5772\/5885"},{"key":"1_CR28","unstructured":"Gutin G, Karapetyan D (2008) Generalized traveling salesman problem reduction algorithms. Preprint in arXiv. http:\/\/arxiv.org\/abs\/0804.0735"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Gutin G, Karapetyan D (2008) Local search heuristics for the multidimensional assignment problem. In: Proceedings of graph theory, computational intelligence and thought, Israel. Lecture Notes in Computer Science (to appear)","DOI":"10.1007\/978-3-642-02029-2_10"},{"key":"1_CR30","unstructured":"Gutin G, Vainshtein A, Yeo A (2002) When greedy-type algorithms fail (unpublished manuscript)"},{"key":"1_CR31","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 (2002) Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Appl Math 119: 107\u2013116","journal-title":"Discrete Appl Math"},{"key":"1_CR32","unstructured":"Gutin G, Yeo A (2005) Graph theory, combinatorics and algorithms: interdisciplinary applications. In: Domination analysis of combinatorial optimization algorithms and problems. Springer, Heidelberg"},{"key":"1_CR33","first-page":"445","volume-title":"Exponential neighborhoods and domination analysis for the TSP","author":"G Gutin","year":"2002","unstructured":"Gutin G, Yeo A, Zverovitch A (2002) The traveling salesman problem and its variations. In: Gutin G, Punnen AP (eds) Exponential neighborhoods and domination analysis for the TSP. Kluwer, Dordrecht, pp 445\u2013487"},{"issue":"8","key":"1_CR34","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1134\/S0005117907080115","volume":"68","author":"P-O Gutman","year":"2007","unstructured":"Gutman P-O, Ioslovich I (2007) On the generalized wolf problem: Preprocessing of nonnegative large-scale linear programming problems with group constraints. Autom Remote Control 68(8): 1401\u20131409","journal-title":"Autom Remote Control"},{"key":"1_CR35","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s002910050098","volume":"21","author":"J Hurink","year":"1999","unstructured":"Hurink J (1999) An exponential neighborhood for a one-machine batching problem. OR Spect 21: 461\u2013476","journal-title":"OR Spect"},{"key":"1_CR36","unstructured":"Johnson DS, McGeoch LA (1995) Local search in combinatorial optimization. In: The traveling salesman problem: a case study in local optimization. Wiley, London, pp 215\u2013310"},{"key":"1_CR37","unstructured":"Johnson DS, McGeoch LA, Rothberg EE (1996) Asymptotic experimental analysis for the held-karp traveling salesman bound. In: SODA \u201996: proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, Philadelphia. Society for Industrial and Applied Mathematics, pp 341\u2013350"},{"key":"1_CR38","unstructured":"Krasnogor N, Smith J (2001) Emergence of profitable search strategies based on a simple inheritance mechanism. In: International genetic and evolutionary computation conference (GECCO2001), San Francisco. Morgan Kaufmann Publishers, Los Altos, pp 432\u2013439"},{"issue":"5","key":"1_CR39","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1109\/TEVC.2005.850260","volume":"9","author":"N Krasnogor","year":"2005","unstructured":"Krasnogor N, Smith JE (2005) A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Trans Evol Comput 9(5): 474\u2013488","journal-title":"IEEE Trans Evol Comput"},{"key":"1_CR40","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The hungarian method for the assignment problem. Naval Res Logistic Q 2: 83\u201397","journal-title":"Naval Res Logistic Q"},{"key":"1_CR41","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1057\/jors.1992.73","volume":"43","author":"G Laporte","year":"1992","unstructured":"Laporte G, Mercure H, Nobert Y (1992) A branch and bound algorithm for a class of asymmetrical vehicle routeing problems. J Oper Res Soc 43: 469\u2013481","journal-title":"J Oper Res Soc"},{"key":"1_CR42","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R (2006) Invitation to fixed parameter algorithms. Oxford University Press, Oxford"},{"key":"1_CR43","first-page":"191","volume":"22","author":"AP Punnen","year":"2001","unstructured":"Punnen AP (2001) The traveling salesman problem: new polynomial approximation algorithms and domination analysis. Inform Optim Sci 22: 191\u2013206","journal-title":"Inform Optim Sci"},{"key":"1_CR44","doi-asserted-by":"crossref","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 complexity. Algorithmica 35: 111\u2013127","journal-title":"Algorithmica"},{"issue":"2","key":"1_CR45","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1016\/j.cie.2008.01.005","volume":"55","author":"F Samanlioglu Jr","year":"2008","unstructured":"Samanlioglu F Jr, Ferrell WG, Kurz ME (2008) A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem. Comput Ind Eng 55(2): 439\u2013449","journal-title":"Comput Ind Eng"},{"key":"1_CR46","unstructured":"Sarvanov VI, Doroshko NN (1981) The approximate solution of the traveling salesman problem by a local algorithm with scanning neighborhoods of factorial cardinality in cubic time. In: Software: algorithms and programs, vol 31. Mathematical Institute of the Belorussian Academy Science Minsk, pp 11\u201313 (in Russian)"},{"key":"1_CR47","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"MWP Savelsbergh","year":"1994","unstructured":"Savelsbergh MWP (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA J Comput 6: 445\u2013454","journal-title":"ORSA J Comput"}],"container-title":["Memetic Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-008-0001-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12293-008-0001-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12293-008-0001-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T03:45:52Z","timestamp":1559447152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12293-008-0001-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,11]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["1"],"URL":"https:\/\/doi.org\/10.1007\/s12293-008-0001-8","relation":{},"ISSN":["1865-9284","1865-9292"],"issn-type":[{"value":"1865-9284","type":"print"},{"value":"1865-9292","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,11]]}}}