{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:16:07Z","timestamp":1770750967697,"version":"3.50.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032111753","type":"print"},{"value":"9783032111760","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,11,23]],"date-time":"2025-11-23T00:00:00Z","timestamp":1763856000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,11,23]],"date-time":"2025-11-23T00:00:00Z","timestamp":1763856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-11176-0_23","type":"book-chapter","created":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T20:11:34Z","timestamp":1763842294000},"page":"399-416","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ulam\u2019s Metric in\u00a0Higher Dimensions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3722-4505","authenticated-orcid":false,"given":"Sebastian","family":"Bala","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3198-4319","authenticated-orcid":false,"given":"Andrzej","family":"Kozik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,23]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D Aldous","year":"1999","unstructured":"Aldous, D., Diaconis, P.: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Am. Math. Soc 36, 413\u2013432 (1999)","journal-title":"Bull. Am. Math. Soc"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1090\/S0894-0347-99-00307-0","volume":"4","author":"J Baik","year":"1999","unstructured":"Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 4, 1119\u20131178 (1999). https:\/\/doi.org\/10.1090\/S0894-0347-99-00307-0","journal-title":"J. Amer. Math. Soc."},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Blum, C., Aguilera, M., Roli, A., Sampels, M.: Hybrid metaheuristics. an emerging approach to optimization. Stud. Comput. Intell. 114 (2008)","DOI":"10.1007\/978-3-540-78295-7"},{"key":"23_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2020.105089","volume":"125","author":"C Blum","year":"2021","unstructured":"Blum, C.: Solving longest common subsequence problems via a transformation to the maximum clique problem. Comput. Oper. Res. 125, 105089 (2021). https:\/\/doi.org\/10.1016\/j.cor.2020.105089","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"23_CR5","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/937503.937505","volume":"35","author":"C Blum","year":"2003","unstructured":"Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268\u2013308 (2003)","journal-title":"ACM Comput. Surv."},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Bona, M.: Combinatorics of Permutations. CRC Press, Inc, Bocaraton (2004)","DOI":"10.1201\/9780203494370"},{"key":"23_CR7","doi-asserted-by":"publisher","unstructured":"Corwin, I.: Commentary on \u201cLongest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem\u201d by David Aldous and Persi Diaconis. Bull. Am. Math. Soc. 55, 363\u2013374 (2018). https:\/\/doi.org\/10.1090\/bull\/1623","DOI":"10.1090\/bull\/1623"},{"key":"23_CR8","doi-asserted-by":"publisher","unstructured":"Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997, pp. 262\u2013273. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/CCC.1997.612321","DOI":"10.1109\/CCC.1997.612321"},{"key":"23_CR9","doi-asserted-by":"publisher","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M Fredman","year":"1975","unstructured":"Fredman, M.: On computing the length of longest increasing subsequences. Discret. Math. 11, 29\u201335 (1975)","journal-title":"Discret. Math."},{"key":"23_CR11","doi-asserted-by":"publisher","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n$$ ^{1-\\epsilon }$$. In: 37th Annual Symposium on Foundations of Computer Science, FOCS\u201996, Burlington, Vermont, USA, 14-16 October, 1996, pp. 627\u2013636. IEEE Computer Society (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548522","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"4","key":"23_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"5","key":"23_CR13","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J Hunt","year":"1977","unstructured":"Hunt, J., Szymanski, T.: A fast algorithm for computing longest common subsequences. Commun. ACM 20(5), 350\u2013353 (1977)","journal-title":"Commun. ACM"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.ejor.2004.02.020","volume":"167","author":"S Imahori","year":"2005","unstructured":"Imahori, S., Yagiura, M., Ibaraki, T.: Improved local search algorithms for the rectangle packing problem with general spatial costs. Eur. J. Oper. Res. 167, 48\u201367 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"23_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-90-481-9591-6","volume-title":"VLSI Physical Design: From Graph Partitioning to Timing Closure","author":"A Kahng","year":"2011","unstructured":"Kahng, A., Lienig, J., Markov, I., Hu, J.: VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, New York (2011)"},{"issue":"3","key":"23_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR17","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 767\u2013775. Association for Computing Machinery (2002). https:\/\/doi.org\/10.1145\/509907.510017","DOI":"10.1145\/509907.510017"},{"issue":"2","key":"23_CR18","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10878-015-9973-8","volume":"33","author":"A Kozik","year":"2015","unstructured":"Kozik, A.: Handling precedence constraints in scheduling problems by the sequence pair representation. J. Comb. Optim. 33(2), 445\u2013472 (2015). https:\/\/doi.org\/10.1007\/s10878-015-9973-8","journal-title":"J. Comb. Optim."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.cor.2017.03.011","volume":"84","author":"A Kozik","year":"2017","unstructured":"Kozik, A.: Scheduling under the network of temporo-spatial proximity relationships. Comput. Oper. Res. 84, 106\u2013115 (2017). https:\/\/doi.org\/10.1016\/j.cor.2017.03.011","journal-title":"Comput. Oper. Res."},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"1518","DOI":"10.1109\/43.552084","volume":"15","author":"H Murata","year":"1996","unstructured":"Murata, H., Fujiyoshi, K., Nakatake, S., Kajitani, Y.: VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. on CAD of ICs. 15, 1518\u20131524 (1996)","journal-title":"IEEE Trans. on CAD of ICs."},{"key":"23_CR21","unstructured":"Papadimitriou, C.: Computational complexity. Addison-Wesley, Reading, Massachusetts (1994)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Pinedo, M.: Scheduling. Theory, Algorithms, and Systems. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-2361-4"},{"key":"23_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139872003","volume-title":"The Surprising Mathematics of Longest Increasing Subsequences","author":"D Romik","year":"2015","unstructured":"Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences. Cambridge University Press, New York (2015)"},{"key":"23_CR24","unstructured":"Sheng, Y., Takahashi, A., Ueno, S.: 2-Stage Simulated Annealing with Crossover Operator for 3D-Packing Volume Minimization (2021)"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D.: The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelfia (2002)","DOI":"10.1137\/1.9780898718515"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1146\/annurev.bb.01.060172.001425","volume":"1","author":"S Ulam","year":"1972","unstructured":"Ulam, S.: Some ideas and prospects in biomathematics. Ann. Rev. Biophys. Bioeng. 1, 277\u2013292 (1972)","journal-title":"Ann. Rev. Biophys. Bioeng."},{"key":"23_CR27","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"issue":"1","key":"23_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11176-0_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T11:09:27Z","timestamp":1770721767000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11176-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,23]]},"ISBN":["9783032111753","9783032111760"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11176-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,23]]},"assertion":[{"value":"23 November 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marrakesh","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Morocco","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ictac2025.digital-hub.sh\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}