{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:11Z","timestamp":1740109331254,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T00:00:00Z","timestamp":1704326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T00:00:00Z","timestamp":1704326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"DFG","award":["439522729","439637648"],"award-info":[{"award-number":["439522729","439637648"]}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["ACT210005"],"award-info":[{"award-number":["ACT210005"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fondecyt","award":["11190789"],"award-info":[{"award-number":["11190789"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10107-023-02044-1","type":"journal-article","created":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T14:02:06Z","timestamp":1704376926000},"page":"479-495","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A 2-approximation for the bounded treewidth sparsest cut problem in $$\\textsf{FPT}$$ Time"],"prefix":"10.1007","volume":"206","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0817-7356","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,4]]},"reference":[{"key":"2044_CR1","doi-asserted-by":"crossref","unstructured":"Aprile, M., Drescher, M., Fiorini, S., Huynh, T.: A tight approximation algorithm for the cluster vertex deletion problem. In: Integer Programming and Combinatorial Optimization (IPCO), (2021)","DOI":"10.1007\/978-3-030-73879-2_24"},{"issue":"1","key":"2044_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0894-0347-07-00573-5","volume":"21","author":"S Arora","year":"2008","unstructured":"Arora, S., Lee, J., Naor, A.: Euclidean distortion and the sparsest cut. J. Am. Math. Soc. 21(1), 1\u201321 (2008)","journal-title":"J. Am. Math. Soc."},{"issue":"2","key":"2044_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 1\u201337 (2009)","journal-title":"J. ACM"},{"issue":"2","key":"2044_CR4","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1137\/15M1054079","volume":"28","author":"D Bienstock","year":"2018","unstructured":"Bienstock, D., Munoz, G.: LP formulations for polynomial optimization problems. SIAM J. Opt. 28(2), 1121\u20131150 (2018)","journal-title":"SIAM J. Opt."},{"issue":"1","key":"2044_CR5","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.disopt.2004.03.002","volume":"1","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Ozbay, N.: Tree-width and the Sherali-Adams operator. Discr. Optim. 1(1), 13\u201321 (2004)","journal-title":"Discr. Optim."},{"key":"2044_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Nc-algorithms for graphs with small treewidth. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), (1988)","DOI":"10.1007\/3-540-50728-0_32"},{"key":"2044_CR7","doi-asserted-by":"crossref","unstructured":"Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge university press, (2004)","DOI":"10.1017\/CBO9780511804441"},{"key":"2044_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Jaffe, A., Lee, J.\u00a0R., Vincent, J.: Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. In: IEEE Symposium on Foundations of Computer Science (FOCS), (2008)","DOI":"10.1109\/FOCS.2008.79"},{"key":"2044_CR9","unstructured":"Chalermsook, P., Kaul, M., Mnich, M., Spoerhase, J., Uniyal, S., Vaz, D.: Approximating sparsest cut in low-treewidth graphs via combinatorial diameter. CoRR, 2111.06299, (2021)"},{"issue":"2","key":"2044_CR10","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94\u2013114 (2006)","journal-title":"Comput. Complex."},{"issue":"2","key":"2044_CR11","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jctb.2012.11.002","volume":"103","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Combin. Theor. Ser. B 103(2), 248\u2013273 (2013)","journal-title":"J. Combin. Theor. Ser. B"},{"key":"2044_CR12","doi-asserted-by":"crossref","unstructured":"Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cut in graphs of bounded treewidth. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), (2010)","DOI":"10.1007\/978-3-642-15369-3_10"},{"key":"2044_CR13","unstructured":"Cohen-Addad, V., Gupta, V., Klein, P.\u00a0N., Li, J.: A quasipolynomial $$(2+\\varepsilon )$$-approximation for planar sparsest cut. In: ACM Symposium on Theory of Computing (STOC), (2021)"},{"issue":"1","key":"2044_CR14","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF02124750","volume":"5","author":"RM Corless","year":"1996","unstructured":"Corless, R.M., Gonnet, G.H., Hare, D.E., Jeffrey, D.J., Knuth, D.E.: On the Lambertw function. Adv. Comput. Math. 5(1), 329\u2013359 (1996)","journal-title":"Adv. Comput. Math."},{"key":"2044_CR15","doi-asserted-by":"crossref","unstructured":"Davies, S., Kulkarni, J., Rothvoss, T., Tarnawski, J., Zhang, Y.: Scheduling with communication delays via lp hierarchies and clustering ii: Weighted completion times on related machines. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), (2021)","DOI":"10.1137\/1.9781611976465.176"},{"key":"2044_CR16","unstructured":"Garg, S.: Quasi-ptas for scheduling with precedences using LP hierarchies. In: International Colloquium on Automata, Languages, and Programming (ICALP), (2018)"},{"issue":"2","key":"2044_CR17","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and $$\\ell _1$$-embeddings of graphs. Combinatorica 24(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"key":"2044_CR18","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: ACM Symposium on Theory of Computing (STOC), (2013)","DOI":"10.1145\/2488608.2488644"},{"issue":"1","key":"2044_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629614","volume":"62","author":"SA Khot","year":"2015","unstructured":"Khot, S.A., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into $$\\ell _1$$. J. ACM 62(1), 1\u201339 (2015)","journal-title":"J. ACM"},{"key":"2044_CR20","unstructured":"Klein, P., Agrawal, A., Ravi, R., Rao, S.: Approximation through multicommodity flow. In: IEEE Symposium on Foundations of Computer Science (FOCS), (1990)"},{"issue":"2","key":"2044_CR21","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01200755","volume":"15","author":"P Klein","year":"1995","unstructured":"Klein, P., Rao, S., Agrawal, A., Ravi, R.: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications. Combinatorica 15(2), 187\u2013202 (1995)","journal-title":"Combinatorica"},{"key":"2044_CR22","doi-asserted-by":"crossref","unstructured":"Korhonen, T., Lokshtanov, D.: An improved parameterized algorithm for treewidth. In: ACM Symposium on Theory of Computing (STOC), pp. 528\u2013541, (2023)","DOI":"10.1145\/3564246.3585245"},{"issue":"2","key":"2044_CR23","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s00454-009-9172-4","volume":"43","author":"JR Lee","year":"2010","unstructured":"Lee, J.R., Raghavendra, P.: Coarse differentiation and multi-flows in planar graphs. Discr. Comput. Geom. 43(2), 346\u2013362 (2010)","journal-title":"Discr. Comput. Geom."},{"issue":"3","key":"2044_CR24","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00493-013-2685-8","volume":"33","author":"JR Lee","year":"2013","unstructured":"Lee, J.R., Sidiropoulos, A.: Pathwidth, trees, and random embeddings. Combinatorica 33(3), 349\u2013374 (2013)","journal-title":"Combinatorica"},{"key":"2044_CR25","doi-asserted-by":"crossref","unstructured":"Magen, A., Moharrami, M.: Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM), (2009)","DOI":"10.1007\/978-3-642-03685-9_20"},{"key":"2044_CR26","doi-asserted-by":"crossref","unstructured":"Maiti, B., Rajaraman, R., Stalfa, D., Svitkina, Z., Vijayaraghavan, A.: Scheduling precedence-constrained jobs on related machines with communication delay. In: IEEE Symposium on Foundations of Computer Science (FOCS), (2020)","DOI":"10.1109\/FOCS46700.2020.00082"},{"issue":"1\u20132","key":"2044_CR27","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","volume":"27","author":"DW Matula","year":"1990","unstructured":"Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discr. Appl. Math. 27(1\u20132), 113\u2013123 (1990)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"2044_CR28","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H Okamura","year":"1981","unstructured":"Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Combin. Theor. Ser. B 31(1), 75\u201381 (1981)","journal-title":"J. Combin. Theor. Ser. B"},{"issue":"3","key":"2044_CR29","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discr. Math."},{"key":"2044_CR30","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/s10107-020-01511-3","volume":"183","author":"V Verdugo","year":"2020","unstructured":"Verdugo, V., Verschae, J., Wiese, A.: Breaking symmetries to rescue sum of squares in the case of makespan scheduling. Math. Program. 183, 583\u2013618 (2020)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02044-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02044-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02044-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:23:24Z","timestamp":1721823804000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02044-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,4]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2044"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02044-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,1,4]]},"assertion":[{"value":"22 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}