{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:52:41Z","timestamp":1743025961352,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031069000"},{"type":"electronic","value":"9783031069017"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-06901-7_9","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"112-125","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in $$\\mathsf {FPT}$$ Time"],"prefix":"10.1007","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]},{"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,27]]},"reference":[{"key":"9_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\/s10107-021-01744-w"},{"issue":"1","key":"9_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."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2), 5:1\u20135:37 (2009)","DOI":"10.1145\/1502793.1502794"},{"issue":"2","key":"9_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. Optim. 28(2), 1121\u20131150 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"9_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. Discret. Optim. 1(1), 13\u201321 (2004)","journal-title":"Discret. Optim."},{"key":"9_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Jaffe, A., Lee, J.R., 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":"9_CR8","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":"9_CR9","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":"9_CR10","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. Comb. Theory Ser. B 103(2), 248\u2013273 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-642-15369-3_10","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E Chlamtac","year":"2010","unstructured":"Chlamtac, E., Krauthgamer, R., Raghavendra, P.: Approximating sparsest cut in graphs of bounded treewidth. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX\/RANDOM 2010. LNCS, vol. 6302, pp. 124\u2013137. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15369-3_10"},{"key":"9_CR12","unstructured":"Cohen-Addad, V., Gupta, A., Klein, P.N., Li, J.: A quasipolynomial $$(2+\\varepsilon )$$-approximation for planar sparsest cut. In: ACM Symposium on Theory of Computing (STOC) (2021)"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., M\u00f6mke, T., Verdugo, V.: A 2-approximation for the bounded treewidth sparsest cut problem in FPT time. CoRR 2111.06163 (2021)","DOI":"10.1007\/978-3-031-06901-7_9"},{"key":"9_CR14","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":"9_CR15","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":"9_CR16","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":"9_CR17","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":"9_CR18","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":"9_CR19","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":"9_CR20","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"},{"issue":"2","key":"9_CR21","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. Discret. Comput. Geom. 43(2), 346\u2013362 (2010)","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"9_CR22","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). https:\/\/doi.org\/10.1007\/s00493-013-2685-8","journal-title":"Combinatorica"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-03685-9_20","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Magen","year":"2009","unstructured":"Magen, A., Moharrami, M.: Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\/RANDOM 2009. LNCS, vol. 5687, pp. 258\u2013271. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_20"},{"key":"9_CR24","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":"9_CR25","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. Discret. Appl. Math. 27(1\u20132), 113\u2013123 (1990)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"9_CR26","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. Comb. Theory Seri. B 31(1), 75\u201381 (1981)","journal-title":"J. Comb. Theory Seri. B"},{"issue":"3","key":"9_CR27","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. Discret. Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discret. Math."},{"key":"9_CR28","doi-asserted-by":"publisher","unstructured":"Verdugo, V., Verschae, J., Wiese, A.: Breaking symmetries to rescue sum of squares in the case of makespan scheduling. Math. Program. (3), 583\u2013618 (2020). https:\/\/doi.org\/10.1007\/s10107-020-01511-3","DOI":"10.1007\/s10107-020-01511-3"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-06901-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T23:03:32Z","timestamp":1653951812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ipco2022.com\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"93","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}