{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:15:40Z","timestamp":1760015740271},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T00:00:00Z","timestamp":1131580800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,3]]},"DOI":"10.1007\/s10107-005-0668-2","type":"journal-article","created":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T19:57:22Z","timestamp":1131652642000},"page":"1-23","source":"Crossref","is-referenced-by-count":18,"title":["Optimal 3-terminal cuts and linear programming"],"prefix":"10.1007","volume":"106","author":[{"given":"Kevin K. H.","family":"Cheung","sequence":"first","affiliation":[]},{"given":"William H.","family":"Cunningham","sequence":"additional","affiliation":[]},{"given":"Lawrence","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,11,10]]},"reference":[{"key":"668_CR1","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for MULTIWAY CUT. Proc. ACM Symp. Theory Comput. 1998, pp. 48\u201352","DOI":"10.1145\/276698.276711"},{"key":"668_CR2","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for MULTIWAY CUT. J. Comput. Syst. Sci. 60, 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"668_CR3","unstructured":"Cheung, K.K.H., Cunningham, W.H., Tang, L.: Optimal 3-terminal cuts and linear programming. Technical Report CORR 2002-24, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, August 2002"},{"key":"668_CR4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.3230210106","volume":"21","author":"Chopra","year":"1991","unstructured":"Chopra, S., Rao, M.R.: On the multiway cut polyhedron. Networks 21, 51\u201389 (1991)","journal-title":"Networks"},{"key":"668_CR5","doi-asserted-by":"crossref","unstructured":"Cunningham, W.H.: The optimal multiterminal cut problem. In: C. Monma, F. Hwang (eds.), Reliability of Computer and Communications Networks, American Math. Soc., 1991, pp. 105\u2013120","DOI":"10.1090\/dimacs\/005\/07"},{"key":"668_CR6","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-48777-8_9","volume":"1610","author":"Cunningham","year":"1999","unstructured":"Cunningham, W.H., Tang, L.: Optimal 3-terminal cuts and linear programming, Integer programming and combinatorial optimization. Lecture Notes in Comput. Sci. 1610, 114\u2013125 (1999)","journal-title":"Lecture Notes in Comput. Sci."},{"key":"668_CR7","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The Complexity of multiway cuts, extended abstract, 1983"},{"key":"668_CR8","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The Complexity of multiterminal cuts. SIAM J. Comput. 23, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"668_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0020-0190(00)00065-X","volume":"75","author":"Freund","year":"2000","unstructured":"Freund, A., Karloff, H.: A lower bound of on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut. Inf. Process. Lett. 75, 43\u201350 (2000)","journal-title":"Inf. Process. Lett."},{"key":"668_CR10","doi-asserted-by":"crossref","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. Proc. ACM Symp. Theory Comput. 1999, pp. 668\u2013678","DOI":"10.1145\/301250.301430"},{"key":"668_CR11","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"Karger","year":"2004","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res. 29, 436\u2013461 (2004)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0668-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-005-0668-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-005-0668-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:50:00Z","timestamp":1559123400000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-005-0668-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,10]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["668"],"URL":"https:\/\/doi.org\/10.1007\/s10107-005-0668-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11,10]]}}}