{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:15Z","timestamp":1740109275192,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T00:00:00Z","timestamp":1564358400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T00:00:00Z","timestamp":1564358400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Hungarian National Research, Development and Innovation Office","award":["NKFIH K109240","K120254"],"award-info":[{"award-number":["NKFIH K109240","K120254"]}]},{"name":"New National Excellence Program of the Ministry of Human Capacities","award":["UNKP-17-4"],"award-info":[{"award-number":["UNKP-17-4"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319376"],"award-info":[{"award-number":["CCF-1319376"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s10107-019-01417-9","type":"journal-article","created":{"date-parts":[[2019,7,29]],"date-time":"2019-07-29T02:02:49Z","timestamp":1564365769000},"page":"411-443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A tight $$\\sqrt{2}$$-approximation for linear 3-cut"],"prefix":"10.1007","volume":"184","author":[{"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vivek","family":"Madan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,29]]},"reference":[{"key":"1417_CR1","unstructured":"B\u00e9rczi, K., Chandrasekaran, K., Kir\u00e1ly, K., Lee, E., Xu, C.: Global and fixed-terminal cuts in digraphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a081, pp. 2:1\u20132:20 (2017)"},{"issue":"1","key":"1417_CR2","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s10107-016-1025-3","volume":"161","author":"A Bern\u00e1th","year":"2017","unstructured":"Bern\u00e1th, A., Pap, G.: Blocking optimal arborescences. Math. Program. 161(1), 583\u2013601 (2017)","journal-title":"Math. Program."},{"key":"1417_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kamath, S., Kannan, S., Viswanath, P.: Delay-constrained unicast and the triangle-cast problem. In: IEEE International Symposium on Information Theory (ISIT), pp. 804\u2013808 (2015)","DOI":"10.1109\/ISIT.2015.7282566"},{"key":"1417_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Madan, V.: Approximating multicut and the demand graph. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 855\u2013874 (2017)","DOI":"10.1137\/1.9781611974782.54"},{"issue":"1","key":"1417_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-005-0668-2","volume":"106","author":"K Cheung","year":"2006","unstructured":"Cheung, K., Cunningham, W., Tang, L.: Optimal 3-terminal cuts and linear programming. Math. Program. 106(1), 1\u201323 (2006)","journal-title":"Math. Program."},{"issue":"4","key":"1417_CR6","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"1417_CR7","doi-asserted-by":"crossref","unstructured":"Ene, A., Vondr\u00e1k, J., Wu, Y.: Local distribution and the symmetry gap: approximability of multiway partitioning problems. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 306\u2013325 (2013)","DOI":"10.1137\/1.9781611973105.23"},{"key":"1417_CR8","unstructured":"Erbacher, R., Jaeger, T., Talele, N., Teutsch, J.: Directed multicut with linearly ordered terminals (2014). Preprint \nhttps:\/\/arxiv.org\/abs\/1407.7498"},{"issue":"1","key":"1417_CR9","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N Garg","year":"2004","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49\u201361 (2004)","journal-title":"J. Algorithms"},{"issue":"6","key":"1417_CR10","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"1417_CR11","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1287\/moor.1030.0086","volume":"29","author":"D 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(3), 436\u2013461 (2004)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1417_CR12","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"1417_CR13","unstructured":"Lee, E.: Improved hardness for cut, interdiction, and firefighter problems. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a080, pp. 92:1\u201392:14 (2017)"},{"key":"1417_CR14","doi-asserted-by":"crossref","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"1417_CR15","doi-asserted-by":"crossref","unstructured":"Muthukumaran, D., Rueda, S., Talele, N., Vijayakumar, H., Teutsch, J., Jaeger, T.: Transforming commodity security policies to enforce Clark\u2013Wilson integrity. In: Proceedings of the 28th Annual Computer Security Applications Conference (ACSAC), pp. 269\u2013278 (2012)","DOI":"10.1145\/2420950.2420991"},{"key":"1417_CR16","doi-asserted-by":"crossref","unstructured":"Talele, N., Teutsch, J., Jaeger, T., Erbacher, R.: Using security policies to automate placement of network intrusion prevention. In: Proceedings of the 5th International Symposium on Engineering Secure Software and Systems (ESSoS), pp. 17\u201332 (2013)","DOI":"10.1007\/978-3-642-36563-8_2"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01417-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01417-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01417-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T10:59:56Z","timestamp":1602759596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01417-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,29]]},"references-count":16,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["1417"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01417-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,7,29]]},"assertion":[{"value":"2 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}