{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:52Z","timestamp":1750221232586,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1318242, CCF-1318242"],"award-info":[{"award-number":["CCF-1318242, CCF-1318242"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188772","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1220-1233","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Almost polynomial hardness of node-disjoint paths in grids"],"prefix":"10.1145","author":[{"given":"Julia","family":"Chuzhoy","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]},{"given":"David H. K.","family":"Kim","sequence":"additional","affiliation":[{"name":"University of Chicago, USA"}]},{"given":"Rachit","family":"Nimavat","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Noga Alon Sanjeev Arora Rajsekar Manokaran Dana Moshkovitz and Omri Weinstein. 2011. Inapproximabilty of Densest k-Subgraph from Average Case Hardness.  Noga Alon Sanjeev Arora Rajsekar Manokaran Dana Moshkovitz and Omri Weinstein. 2011. Inapproximabilty of Densest k-Subgraph from Average Case Hardness."},{"key":"e_1_3_2_2_2_1","unstructured":"Matthew Andrews. 2010.  Matthew Andrews. 2010."},{"volume-title":"Proceedings of IEEE FOCS. 277\u2013286","author":"Approximation","key":"e_1_3_2_2_3_1"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2455-9"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060632"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/313651.313820"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365675"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_2_9_1","unstructured":"Andrei Z. Broder Alan M. Frieze Stephen Suen and Eli Upfal. 1998.  Andrei Z. Broder Alan M. Frieze Stephen Suen and Eli Upfal. 1998."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290805"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129727"},{"key":"e_1_3_2_2_12_1","unstructured":"Chandra Chekuri and Julia Chuzhoy. {n. d.}. Half-Integral All-or-Nothing Flow. Unpublished Manuscript.  Chandra Chekuri and Julia Chuzhoy. {n. d.}. Half-Integral All-or-Nothing Flow. Unpublished Manuscript."},{"key":"e_1_3_2_2_13_1","unstructured":"Chandra Chekuri and Alina Ene. 2013.  Chandra Chekuri and Alina Ene. 2013."},{"volume-title":"Approximation for Maximum Node Disjoint Paths with Constant Congestion. In Proc. of ACM-SIAM SODA.","key":"e_1_3_2_2_14_1"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060618"},{"key":"e_1_3_2_2_16_1","unstructured":"Chandra Chekuri Sanjeev Khanna and F. Bruce Shepherd. 2006.  Chandra Chekuri Sanjeev Khanna and F. Bruce Shepherd. 2006."},{"volume-title":"Theory of Computing 2, 1","year":"2006","author":"Approximation An","key":"e_1_3_2_2_17_1"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/060674442"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273343"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910464"},{"volume-title":"Kim","year":"2015","author":"Chuzhoy Julia","key":"e_1_3_2_2_21_1"},{"key":"e_1_3_2_2_22_1","volume-title":"APPROX\/RANDOM 2015, August 24-26","volume":"40","author":"Node-Disjoint On Approximating","year":"2015"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897538"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Julia Chuzhoy David H. K. Kim and Rachit Nimavat. 2017. Improved Approximation Algorithm for Node-Disjoint Paths in Grid Graphs with Sources on Grid Boundary. (2017).  Julia Chuzhoy David H. K. Kim and Rachit Nimavat. 2017. Improved Approximation Algorithm for Node-Disjoint Paths in Grid Graphs with Sources on Grid Boundary. (2017).","DOI":"10.1145\/2897518.2897538"},{"key":"e_1_3_2_2_25_1","unstructured":"Unpublished Manuscript.  Unpublished Manuscript."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055411"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2893472"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"e_1_3_2_2_29_1","unstructured":"Uriel Feige. 2002.  Uriel Feige. 2002."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_2_31_1","unstructured":"Uriel Feige Magn\u00fas M. Halld\u00f3rsson Guy Kortsarz and Aravind Srinivasan. 2003.  Uriel Feige Magn\u00fas M. Halld\u00f3rsson Guy Kortsarz and Aravind Srinivasan. 2003."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700380754"},{"key":"e_1_3_2_2_33_1","unstructured":"Krzysztof Fleszar Matthias Mnich and Joachim Spoerhase. 2016.  Krzysztof Fleszar Matthias Mnich and Joachim Spoerhase. 2016."},{"key":"e_1_3_2_2_34_1","first-page":"1","article-title":") (Leibniz International Proceedings in Informatics (LIPIcs)), Piotr Sankowski and Christos Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl","volume":"42","author":"Maximum Disjoint Paths New Algorithms","year":"2016","journal-title":"Germany"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/338219.338631"},{"key":"e_1_3_2_2_36_1","unstructured":"N. Garg V.V. Vazirani and M. Yannakakis. 1997.  N. Garg V.V. Vazirani and M. Yannakakis. 1997."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_3_2_2_38_1","unstructured":"Thomas Holenstein. 2007.  Thomas Holenstein. 2007."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_3_2_2_41_1","unstructured":"Ken-Ichi Kawarabayashi and Yusuke Kobayashi. 2013.  Ken-Ichi Kawarabayashi and Yusuke Kobayashi. 2013."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438648"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.59"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.18"},{"key":"e_1_3_2_2_45_1","unstructured":"J. Kleinberg and R. Rubinfeld. 1996.  J. Kleinberg and R. Rubinfeld. 1996."},{"volume-title":"Paths in Expander Graphs. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS \u201996)","author":"Short","key":"e_1_3_2_2_46_1"},{"key":"e_1_3_2_2_47_1","unstructured":"Jon M. Kleinberg and \u00c9va Tardos. 1995.  Jon M. Kleinberg and \u00c9va Tardos. 1995."},{"volume-title":"Paths in Densely Embedded Graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. 52\u201361","author":"Disjoint","key":"e_1_3_2_2_48_1"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1579"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"e_1_3_2_2_51_1","unstructured":"MR Kramer and Jan van Leeuwen. 1984.  MR Kramer and Jan van Leeuwen. 1984."},{"volume-title":"Advances in computing research 2","year":"1984","author":"The","key":"e_1_3_2_2_52_1"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061425.1061430"},{"key":"e_1_3_2_2_55_1","unstructured":"Pasin Manurangsi. 2017.  Pasin Manurangsi. 2017."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_3_2_2_57_1","unstructured":"Harald R\u00e4cke. 2002.  Harald R\u00e4cke. 2002."},{"volume-title":"Congestion in General Networks. In Proc. of IEEE FOCS. 43\u201352","author":"Minimizing","key":"e_1_3_2_2_58_1"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374378"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958023"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_2_64_1","unstructured":"N. Robertson and P. D. Seymour. 1990. Outline of a disjoint paths algorithm. In Paths Flows and VLSI-Layout. Springer-Verlag.  N. Robertson and P. D. Seymour. 1990. Outline of a disjoint paths algorithm. In Paths Flows and VLSI-Layout. Springer-Verlag."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.30"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188772","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:08Z","timestamp":1750212428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":66,"alternative-id":["10.1145\/3188745.3188772","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188772","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}