{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:08Z","timestamp":1750219748089,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft","award":["KO 6140\\\/1-2"],"award-info":[{"award-number":["KO 6140\\\/1-2"]}]},{"name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","award":["CZ.02.01.01\\\/00\\\/22_008\\\/0004590"],"award-info":[{"award-number":["CZ.02.01.01\\\/00\\\/22_008\\\/0004590"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649631","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"671-682","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimization with Pattern-Avoiding Input"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3430-5262","authenticated-orcid":false,"given":"Benjamin Aram","family":"Berendsohn","sequence":"first","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3253-2373","authenticated-orcid":false,"given":"L\u00e1szl\u00f3","family":"Kozma","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4389-5807","authenticated-orcid":false,"given":"Michal","family":"Opler","sequence":"additional","affiliation":[{"name":"Czech Technical University, Prague, Czechia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104444776"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972979.1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00812-z"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1015-8"},{"volume-title":"Handbook of enumerative combinatorics. 87","author":"B\u00f3na Mikl\u00f3s","key":"e_1_3_2_1_6_1","unstructured":"Mikl\u00f3s B\u00f3na. 2015. Handbook of enumerative combinatorics. 87, CRC Press."},{"volume-title":"Combinatorics of permutations","author":"B\u00f3na Mikl\u00f3s","key":"e_1_3_2_1_7_1","unstructured":"Mikl\u00f3s B\u00f3na. 2022. Combinatorics of permutations. CRC Press."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.30"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3486655"},{"key":"e_1_3_2_1_10_1","volume-title":"Sebastian Siebertz, and St\u00e9phan Thomass\u00e9.","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, Sebastian Siebertz, and St\u00e9phan Thomass\u00e9. 2021. Twin-width and permutations. arxiv:2102.06880."},{"volume-title":"Online computation and competitive analysis","author":"Borodin Allan","key":"e_1_3_2_1_11_1","unstructured":"Allan Borodin and Ran El-Yaniv. 1998. Online computation and competitive analysis. Cambridge University Press. isbn:978-0-521-56392-5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00209-3"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511902499.003"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21840-3_13"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.32"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2018.55"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch22"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Parinya Chalermsook Seth Pettie and Sorrachai Yingchareonthawornchai. 2023. Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns. arXiv:2307.02294.","DOI":"10.1137\/1.9781611977912.7"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.10.013"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9342-z"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220008"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.06.003"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.150"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.55"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447347"},{"key":"e_1_3_2_1_26_1","unstructured":"Jacob Fox. 2013. Stanley-Wilf limits are typically exponential. arxiv:1310.8378."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90078-5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977066.21"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.12.021"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 23rd European Workshop on Computational Geometry. 174\u2013177","author":"Gudmundsson Joachim","year":"2007","unstructured":"Joachim Gudmundsson, Oliver Klein, Christian Knauer, and Michiel Smid. 2007. Small Manhattan networks and algorithmic applications for the earth mover\u2019s distance. In Proceedings of the 23rd European Workshop on Computational Geometry. 174\u2013177."},{"key":"e_1_3_2_1_32_1","first-page":"219","article-title":"Approximating a Minimum Manhattan Network","volume":"8","author":"Gudmundsson Joachim","year":"2001","unstructured":"Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan. 2001. Approximating a Minimum Manhattan Network. Nord. J. Comput., 8, 2 (2001), 219\u2013232. http:\/\/www.cs.helsinki.fi\/njc\/References\/gudmundssonln:219.html","journal-title":"Nord. J. Comput."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.7"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195911003688"},{"volume-title":"New Bounds on Optimal Binary Search Trees. Ph. D. Dissertation","author":"Harmon Dion","key":"e_1_3_2_1_35_1","unstructured":"Dion Harmon. 2006. New Bounds on Optimal Binary Search Trees. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.79"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40273-9_16"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2018.50"},{"volume-title":"Patterns in permutations and words. 1","author":"Kitaev Sergey","key":"e_1_3_2_1_39_1","unstructured":"Sergey Kitaev. 2011. Patterns in permutations and words. 1, Springer."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04166-6_22"},{"key":"e_1_3_2_1_41_1","volume-title":"The art of computer programming","author":"Knuth Donald Ervin","year":"2018","unstructured":"Donald Ervin Knuth. 1998. The art of computer programming, , Volume III, 2nd Edition. Addison-Wesley. isbn:0201896850 https:\/\/www.worldcat.org\/oclc\/312994415","edition":"2"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.002"},{"key":"e_1_3_2_1_43_1","volume-title":"Binary search trees and rectangulations. CoRR, abs\/1603.08151","author":"Kozma L\u00e1szl\u00f3","year":"2016","unstructured":"L\u00e1szl\u00f3 Kozma and Thatchaphol Saranurak. 2016. Binary search trees and rectangulations. CoRR, abs\/1603.08151 (2016), arXiv:1603.08151."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1195188"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.80"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9_37"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90003-W"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCTA.2004.04.002"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20840"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2022.52"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch24"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12143"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579253"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218004"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649631","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:47Z","timestamp":1750178207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":55,"alternative-id":["10.1145\/3618260.3649631","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649631","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}