{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:54Z","timestamp":1781345694735,"version":"3.54.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T00:00:00Z","timestamp":1522368000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T00:00:00Z","timestamp":1522368000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526799"],"award-info":[{"award-number":["CCF-1526799"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hungarian National Research, Development and Innovation Office","award":["NKFIH K109240"],"award-info":[{"award-number":["NKFIH K109240"]}]},{"name":"Hungarian National Research, Development and Innovation Office","award":["K120254"],"award-info":[{"award-number":["K120254"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s10107-018-1270-8","type":"journal-article","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T02:28:41Z","timestamp":1522376921000},"page":"291-320","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Beating the 2-approximation factor for global bicut"],"prefix":"10.1007","volume":"177","author":[{"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karthekeyan","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tam\u00e1s","family":"Kir\u00e1ly","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,3,30]]},"reference":[{"key":"1270_CR1","doi-asserted-by":"crossref","unstructured":"Angelidakis, H., Makarychev, Y., Manurangsi, P.: An improved integrality gap for the C\u0103linescu\u2013Karloff\u2013Rabani relaxation for multiway cut. In: Proceedings of the 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO\u201917, pp. 40\u201350 (2017)","DOI":"10.1007\/978-3-319-59250-3_4"},{"key":"1270_CR2","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\u201917, pp. 855\u2013874 (2017)","DOI":"10.1137\/1.9781611974782.54"},{"issue":"1","key":"1270_CR3","doi-asserted-by":"publisher","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":"3","key":"1270_CR4","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564\u2013574 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1270_CR5","doi-asserted-by":"publisher","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":"1270_CR6","unstructured":"Erbacher, R., Jaeger, T., Talele, N., Teutsch, J.: Directed multicut with linearly ordered terminals. Preprint: \n                              arXiv:1407.7498\n                              \n                            (2014)"},{"key":"1270_CR7","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Proceedings of the 20th International Colloquium on Automata, Languages and Programming, ICALP\u201994, pp. 487\u2013498 (1994)","DOI":"10.1007\/3-540-58201-0_92"},{"issue":"1","key":"1270_CR8","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1270_CR9","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."},{"key":"1270_CR10","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R.: Derandomization through approximation. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC\u201994, pp. 497\u2013506 (1994)","DOI":"10.1145\/195058.195241"},{"issue":"4","key":"1270_CR11","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D Karger","year":"1996","unstructured":"Karger, D., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"1270_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC\u201902, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"1270_CR13","unstructured":"Lee, E.: Improved hardness for cut, interdiction, and firefighter problems. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 92:1\u201392:14 (2017)"},{"key":"1270_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\u201908, pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"1270_CR15","unstructured":"Queyranne, M.: On optimum $$k$$-way partitions with submodular costs and minimum part-size constraints. Talk Slides, \n                              https:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43309\/Queyranne.pdf\n                              \n                            (2012). Accessed 26 Mar 2018"},{"issue":"1","key":"1270_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding k cuts within twice the optimal. SIAM J. Comput. 24(1), 101\u2013108 (1995)","journal-title":"SIAM J. Comput."},{"key":"1270_CR17","doi-asserted-by":"crossref","unstructured":"Sharma, A., Vondr\u00e1k, J.: Multiway cut, pairwise realizable distributions, and descending thresholds. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC\u201914, pp. 724\u2013733 (2014)","DOI":"10.1145\/2591796.2591866"},{"key":"1270_CR18","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Minimum $$k$$-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC\u201908, pp. 159\u2013166 (2008)","DOI":"10.1145\/1374376.1374402"},{"key":"1270_CR19","doi-asserted-by":"crossref","unstructured":"Vazirani, V., Yannakakis, M.: Suboptimal cuts: their enumeration, weight and number (extended abstract). In: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP\u201992, pp. 366\u2013377 (1992)","DOI":"10.1007\/3-540-55719-9_88"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1270-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1270-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1270-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:38:21Z","timestamp":1589647101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1270-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,30]]},"references-count":19,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["1270"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1270-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,30]]},"assertion":[{"value":"29 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}