{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T13:51:21Z","timestamp":1768744281702,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1993,6,1]],"date-time":"1993-06-01T00:00:00Z","timestamp":738892800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1993,6]]},"DOI":"10.1007\/bf01580607","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T05:43:41Z","timestamp":1114667021000},"page":"145-166","source":"Crossref","is-referenced-by-count":121,"title":["Survivable networks, linear programming relaxations and the parsimonious property"],"prefix":"10.1007","volume":"60","author":[{"given":"Michel X.","family":"Goemans","sequence":"first","affiliation":[]},{"given":"Dimitris J.","family":"Bertsimas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"A. Agrawal, P. Klein and R. Ravi, \u201cWhen trees collide: An approximation algorithm for the generalized Steiner problem in networks,\u201d in:Proceedings of the 23rd ACM Symposium on Theory of Computing (1991) pp. 134\u2013144.","DOI":"10.1145\/103418.103437"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y.P. Aneja","year":"1980","unstructured":"Y.P. Aneja, \u201cAn integer linear programming approach to the Steiner problem in graphs,\u201dNetworks 10 (1980) 167\u2013178.","journal-title":"Networks"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1287\/opre.37.5.716","volume":"37","author":"A. Balakrishnan","year":"1989","unstructured":"A. Balakrishnan, T.L. Magnanti and R.T. Wong, \u201cA dual-ascent procedure for large-scale uncapacitated network design,\u201dOperations Research 37 (1989) 716\u2013740.","journal-title":"Operations Research"},{"key":"CR4","first-page":"361","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"E. Balas","year":"1985","unstructured":"E. Balas and P. Toth, \u201cBranch and Bound methods,\u201d in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985) pp. 361\u2013401."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D. Bienstock","year":"1993","unstructured":"D. Bienstock, M.X. Goemans, D. Simchi-Levi and D.P. Williamson, \u201cA note on the prize collecting traveling salesman problem,\u201dMathematical Programming 59 (1993) 413\u2013420.","journal-title":"Mathematical Programming"},{"key":"CR6","volume-title":"\u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical Report, GSIA","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical Report, GSIA, Carnegie-Mellon University (Pittsburgh, PA, 1976)."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G. Cornuejols","year":"1977","unstructured":"G. Cornuejols, M.L. Fisher and G.L. Nemhauser, \u201cLocation of bank accounts to optimize float,\u201dManagement Science 23 (1977) 789\u2013810.","journal-title":"Management Science"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cMaximum matching and a polyhedron with 0\u20131 vertices,\u201dJournal of Research of the National Bureau of Standards 69B (1965) 125\u2013130.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"CR9","first-page":"69","volume-title":"Combinatorial Structures and their Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, \u201cSubmodular functions, matroids and certain polyhedra,\u201d in: R. Guy et al., eds.,Combinatorial Structures and their Applications (Gordon and Breach, London, 1970), pp. 69\u201387."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1051\/ro\/1978120202071","volume":"12","author":"C. El-Arbi","year":"1978","unstructured":"C. El-Arbi, \u201cUne heuristique pour le probl\u00e8me de l'arbre de Steiner,\u201dRAIRO Operations Research 12 (1978) 207\u2013212.","journal-title":"RAIRO Operations Research"},{"key":"CR11","volume-title":"Communication, Transmission and Transportation Networks","author":"H. Frank","year":"1971","unstructured":"H. Frank and I.T. Frisch,Communication, Transmission and Transportation Networks (Addison-Wesley, Reading, MA, 1971)."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1287\/moor.16.1.72","volume":"16","author":"M.X. Goemans","year":"1991","unstructured":"M.X. Goemans and D. Bertsimas, \u201cProbabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem,\u201dMathematics of Operations Research 16 (1991) 72\u201389.","journal-title":"Mathematics of Operations Research"},{"key":"CR13","unstructured":"M.X. Goemans and D.P. Williamson, \u201cA general approximation technique for constrained forest problems,\u201d in:Proceedings of the third ACM-SIAM Symposium on Discrete Algorithms (1992) pp. 307\u2013315."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"R.E. Gomory and T.C. Hu, \u201cSynthesis of a communication network,\u201dSIAM Journal on Applied Mathematics 9 (1961) 551\u2013570.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R.M. Karp, \u201cThe traveling-salesman problem and minimum spanning trees,\u201dOperations Research 18 (1970) 1138\u20131162.","journal-title":"Operations Research"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R.M. Karp, \u201cThe traveling salesman problem and minimum spanning trees: Part II,\u201dMathematical Programming 1 (1971) 6\u201325.","journal-title":"Mathematical Programming"},{"key":"CR17","unstructured":"D. Johnson, talk presented at theMathematical Programming Symposium, Tokyo (1988)."},{"key":"CR18","unstructured":"D. Johnson, personal communication (1989)."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems\u201d, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of Computer Computations (Plenum, New York, 1972) pp. 85\u2013103."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R.M. Karp","year":"1977","unstructured":"R.M. Karp, \u201cProbabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane,\u201dMathematics of Operations Research 2 (1977) 209\u2013224.","journal-title":"Mathematics of Operations Research"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"L. Kou, G. Markowsky and L. Berman, \u201cA fast algorithm for Steiner trees,\u201dActa Informatica 15 (1981) 141\u2013145.","journal-title":"Acta Informatica"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"J.B. Kruskal, \u201cOn the shortest spanning subtree of a graph and the traveling salesman problem,\u201dProceedings of the American Mathematical Society 7 (1956) 48\u201350.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"CR23","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","year":"1985","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985)."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L. Lov\u00e1sz","year":"1976","unstructured":"L. Lov\u00e1sz, \u201cOn some connectivity properties of Eulerian graphs,\u201dActa Mathematica Academiae Scientiarum Hungaricae 28 (1976) 129\u2013138.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"CR25","first-page":"185","volume":"31","author":"N. Maculan","year":"1987","unstructured":"N. Maculan, \u201cThe Steiner problem in graphs,\u201dAnnals of Discrete Mathematics 31 (1987) 185\u2013212.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K. Mehlhorn","year":"1988","unstructured":"K. Mehlhorn, \u201cA faster approximation algorithm for the Steiner problem in graphs,\u201dInformation Processing Letters 27 (1988) 125\u2013128.","journal-title":"Information Processing Letters"},{"key":"CR27","volume-title":"Methods for designing survivable communication networks","author":"C.L. Monma","year":"1989","unstructured":"C.L. Monma and C.-W. Ko, \u201cMethods for designing survivable communication networks,\u201d NATO Advanced Research Workshop (Denmark, 1989)."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01585735","volume":"46","author":"C.L. Monma","year":"1990","unstructured":"C.L. Monma, B.S. Munson and W.R. Pulleyblank, \u201cMinimum weight two-connected spanning networks,\u201dMathematical Programming 46 (1990) 153\u2013171.","journal-title":"Mathematical Programming"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1287\/opre.37.4.531","volume":"37","author":"C.L. Monma","year":"1989","unstructured":"C.L. Monma and D.F. Shallcross, \u201cMethods for designing communication networks with certain two-connected survivability constraints,\u201dOperations Research 37 (1989) 531\u2013541.","journal-title":"Operations Research"},{"key":"CR30","first-page":"155","volume":"31","author":"J. Plesnik","year":"1981","unstructured":"J. Plesnik, \u201cA bound for the Steiner tree problem in graphs,\u201dMathematica Slovaca 31 (1981) 155\u2013163.","journal-title":"Mathematica Slovaca"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"R.C. Prim, \u201cShortest connection networks and some generalizations,\u201dThe Bell System Technical Journal 36 (1957) 1389\u20131401.","journal-title":"The Bell System Technical Journal"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzalez, \u201cP-complete approximation problems,\u201dJournal of the Association for Computing Machinery 23 (1976) 555\u2013565.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D. Shmoys","year":"1990","unstructured":"D. Shmoys and D. Williamson, \u201cAnalyzing the Held-Karp TSP bound: A monotonicity property with application,\u201dInformation Processing Letters 35 (1990) 281\u2013285.","journal-title":"Information Processing Letters"},{"key":"CR34","volume-title":"\u201cInteger solution to synthesis of communication network,\u201d Technical Report","author":"S. Sridhar","year":"1989","unstructured":"S. Sridhar and R. Chandrasekaran, \u201cInteger solution to synthesis of communication network,\u201d Technical Report, The University of Texas (Dallas, TX, 1989)."},{"key":"CR35","doi-asserted-by":"crossref","unstructured":"K. Steiglitz, P. Weiner and D.J. Kleitman, \u201cThe design of minimum-cost survivable networks,\u201dIEEE Transactions on Circuit Theory CT-16(4) (1969) 455\u2013460.","DOI":"10.1109\/TCT.1969.1083004"},{"key":"CR36","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, \u201cAn approximate solution for the Steiner problem in graphs,\u201dMathematica Japonica 24 (1980) 573\u2013577.","journal-title":"Mathematica Japonica"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"P. Winter, \u201cSteiner problem in networks: a survey,\u201dNetworks 17 (1987) 129\u2013167.","journal-title":"Networks"},{"key":"CR38","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L.A. Wolsey","year":"1980","unstructured":"L.A. Wolsey, \u201cHeuristic analysis, linear programming and Branch and Bound,\u201dMathematical Programming Study 13 (1980) 121\u2013134.","journal-title":"Mathematical Programming Study"},{"key":"CR39","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R.T. Wong","year":"1984","unstructured":"R.T. Wong, \u201cA dual ascent approach for Steiner tree problems on a directed graph,\u201dMathematical Programming 28 (1984) 271\u2013287.","journal-title":"Mathematical Programming"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580607.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01580607\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:12:09Z","timestamp":1556881929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01580607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":39,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["BF01580607"],"URL":"https:\/\/doi.org\/10.1007\/bf01580607","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}