{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,14]],"date-time":"2025-04-14T08:54:00Z","timestamp":1744620840304},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540660194"},{"type":"electronic","value":"9783540487777"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48777-8_10","type":"book-chapter","created":{"date-parts":[[2007,3,2]],"date-time":"2007-03-02T13:43:11Z","timestamp":1172842991000},"page":"126-136","source":"Crossref","is-referenced-by-count":18,"title":["Semidefinite Programming Methods for the Symmetric Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"Drago\u0161","family":"Cvetkovi\u0107","sequence":"first","affiliation":[]},{"given":"Mirjana","family":"\u010cangalovi\u0107","sequence":"additional","affiliation":[]},{"given":"Vera","family":"Kova\u010devi\u0107-Vuj\u010di\u0107","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,4,30]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Borchers, B.: CSDP, A C Library for Semidefinite Programming. Optimization Methods and Software (to appear)","DOI":"10.1080\/10556789908805765"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01589105","volume":"45","author":"G. Carpaneto","year":"1989","unstructured":"Carpaneto G., Fischetti M., Toth P.: New Lower Bounds for the Symmetric Travelling Salesman Problem. Math. Program. 45 (1989) 233\u2013254.","journal-title":"Math. Program"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1137\/0119070","volume":"19","author":"N. Christofides","year":"1970","unstructured":"Christofides N.: The Shortest Hamiltonian Chain of a Graph. SIAM J. Appl. Math. 19 (1970) 689\u2013696.","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR4","volume-title":"Combinatorial Optimization","author":"W. Cook","year":"1998","unstructured":"Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial Optimization. John Wiley & Sons, New York Chichester Weinheim Brisbane Singapore Toronto (1998)"},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H. Crowder","year":"1980","unstructured":"Crowder H., Padberg M.W.: Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality. Management Sci. 26 (1980) 495\u2013509","journal-title":"Management Sci"},{"key":"10_CR6","first-page":"41","volume":"1","author":"D. Cvetkovi\u0107","year":"1990","unstructured":"Cvetkovi\u0107, D., \u010cangalovi\u0107, M., Dimitrijevi\u0107, V., Kraus, L., Milosavljevi\u0107, M., Simi\u0107, S.: TSP-SOLVER-A Programming Package for the Traveling Salesman Problem. Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat., 1 (1990) 41\u201347","journal-title":"Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat."},{"key":"10_CR7","unstructured":"Cvetkovi\u0107, D., \u010cangalovi\u0107, M., Kova\u010devi\u0107-Vuj\u010di\u0107, V.: Semidefinite Programming and Traveling Salesman Problem. In: Petrovi\u0107, R., Radojevi\u0107, D. (eds.): Proceedings of Yugoslav Symposium on Operations Research. Herceg Novi, Yugoslavia (1998) 239\u2013242"},{"key":"10_CR8","unstructured":"Cvetkovi\u0107, D., \u010cangalovi\u0107, M., Kova\u010devi\u0107-Vuj\u010di\u0107, V.: Semidefinite Relaxations of Travelling Salesman Problem. (to appear)"},{"key":"10_CR9","volume-title":"Variations on the Travelling Salesman Theme","author":"D. Cvetkovi\u0107","year":"1996","unstructured":"Cvetkovi\u0107, D., Dimitrijevi\u0107, V., Milosavljevi\u0107, M.: Variations on the Travelling Salesman Theme. Libra Produkt, Belgrade (1996)"},{"key":"10_CR10","volume-title":"Spectra of Graphs","author":"D. Cvetkovi\u0107","year":"1995","unstructured":"Cvetkovi\u0107, D., Doob, M., Sachs, H.: Spectra of Graphs. 3rd edn. Johann Ambrosius Barth, Heidelberg Leipzig (1995)","edition":"3rd edn."},{"key":"10_CR11","first-page":"393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"Dantzig G.B., Fulkerson D.R., Johnson S.M.: Solution of a Large-Scale Traveling Salesman Problem. Operations Research 2 (1954) 393\u2013410","journal-title":"Operations Research"},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"Fiedler M.: Algebraic Connectivity of Graphs. Czechoslovak Math. J. 23 (1973) 298\u2013305","journal-title":"Czechoslovak Math. J."},{"key":"10_CR13","first-page":"57","volume":"25","author":"M. Fiedler","year":"1989","unstructured":"Fiedler, M.: Laplacian of Graphs and Algebraic Connectivity. In: Combinatorics and Graph Theory, Vol. 25, Banach center publications, PWN-Polish scientific publishers Warsaw (1989) 57\u201370","journal-title":"Combinatorics and Graph Theory"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1287\/opre.34.5.698","volume":"34","author":"B. Gavish","year":"1986","unstructured":"Gavish B., Srikanth K.N.: An Optimal Solution Method for Large-Scale Multiple Travelling Salesman Problems. Operations Research 34 (1986) 698\u2013717","journal-title":"Operations Research"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0025-5610(97)00051-8","volume":"79","author":"M. Goemans","year":"1997","unstructured":"Goemans, M.: Semidefinite Programming in Combinatorial Optimization. Math. Program. 79 (1997) 143\u2013161","journal-title":"Math. Program"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans M.X., Williamson D.P.: Improved Approximation Algorithms for Maximum Cut and Satisfability Problems Using Semidefinite Programming. J. ACM 42 (1995) 1115\u20131145","journal-title":"J. ACM"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M. Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel M., Holland O.: Solution of Large-Scale Symmetric Travelling Salesman Problems. Math. Program. 51 (1991) 141\u2013202","journal-title":"Math. Program"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01585505","volume":"7","author":"K. Helbig-Hansen","year":"1974","unstructured":"Helbig-Hansen K., Krarup J.: Improvements of the Held-Karp Algorithm for the Symmetric Traveling Salesman Problem. Math. Program. 7 (1974) 87\u201396","journal-title":"Math. Program"},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"Held M., Karp R.M.: The Travelling Salesman Problem and Minimum Spanning Trees. Part II, Math. Program. 1 (1971) 6\u201325","journal-title":"Part II, Math. Program"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D. Karger","year":"1998","unstructured":"Karger D., Motwani R., Sudan M.: Approximate Graph Coloring by Semidefinite Programming. J. ACM 45 (1998) 246\u2013265","journal-title":"J. ACM"},{"key":"10_CR21","unstructured":"Land A.H.: The Solution of Some 100-City Travelling Salesman Problems. Working Paper. London School of Economics (1979)"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0377-2217(92)90138-Y","volume":"59","author":"G. Laporte","year":"1992","unstructured":"Laporte, G.: The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms. European J. Operational Research 59 (1992) 231\u2013247","journal-title":"European J. Operational Research"},{"key":"10_CR23","unstructured":"Laporte G.: Exact Algorithms for the Traveling Salesman Problem and the Vehicle Routing Problem. Les Cahiers du GERAD G-98-37 July (1998)"},{"key":"10_CR24","volume-title":"The Traveling Salesman Problem","author":"E.L. Lawler","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem. John Wiley & Sons, Chichester New York Brisbane Toronto Singapore (1985)"},{"key":"10_CR25","volume-title":"Solving the Travelling Salesman Problem by Integer Programming","author":"G.T. Martin","year":"1966","unstructured":"Martin G.T.: Solving the Travelling Salesman Problem by Integer Programming. Working Paper. CEIR, New York (1966)"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01580682","volume":"10","author":"P. Miliotis","year":"1976","unstructured":"Miliotis P.: Integer Programming Approaches to the Travelling Salesman Problem. Math. Program. 10 (1976) 367\u2013378","journal-title":"Math. Program"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01609016","volume":"15","author":"P. Miliotis","year":"1978","unstructured":"Miliotis P.: Using Cuting Planes to Solve the Symmetric Travelling Salesman Problem. Math. Program. 15 (1978) 177\u2013188","journal-title":"Math. Program"},{"key":"10_CR28","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120888","volume":"12","author":"M.W. Padberg","year":"1980","unstructured":"Padberg M.W., Hong S.: On the Symmetric Travelling Salesman Problem: A Computational Study. Math. Program. Study 12 (1980) 78\u2013107","journal-title":"Math. Program. Study"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","volume":"6","author":"M.W. Padberg","year":"1987","unstructured":"Padberg M.W., Rinaldi G.: Optimization of a 532-City Symmetric Traveling Salesman Problem by Branch and Cut. Operations Research Letters 6 (1987) 1\u20137","journal-title":"Operations Research Letters"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1137\/1033004","volume":"33","author":"M.W. Padberg","year":"1991","unstructured":"Padberg M.W., Rinaldi G.: A Branch-and-Cut Algorithm for the Resolution of Large Scale Symmetric Traveling Salesman Problems. SIAM Review 33 (1991) 66\u2013100","journal-title":"SIAM Review"},{"key":"10_CR31","unstructured":"Rendl, F.: Semidefinite Programming and Combinatorial Optimization. Technical Report Woe-19, TU Graz, Austria December (1997)"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1016\/S0167-5060(08)70754-4","volume":"1","author":"T.H.C. Smith","year":"1977","unstructured":"Smith T.H.C., Thompson G.L.: A LIFO Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem Using Held and Karp\u2019s 1-Tree Relaxation. Annals Disc. Math. 1 (1977) 479\u2013493","journal-title":"Annals Disc. Math."},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L. Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite Programming. SIAM Review 38 (1996) 49\u201395","journal-title":"SIAM Review"},{"key":"10_CR34","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0377-2217(82)90015-7","volume":"9","author":"T. Volgenant","year":"1982","unstructured":"Volgenant T., Jonker R.: A Branch and Bound Algorithm for the Symmetric Traveling Salesman Problem Based on the 1-Tree Relaxation. Europian J. Operational Research 9 (1982) 83\u201389","journal-title":"Europian J. Operational Research"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48777-8_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,9]],"date-time":"2021-08-09T10:44:01Z","timestamp":1628505841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48777-8_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540660194","9783540487777"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-48777-8_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}