{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T09:54:56Z","timestamp":1781603696041,"version":"3.54.5"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T00:00:00Z","timestamp":1781568000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T00:00:00Z","timestamp":1781568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,9]]},"abstract":"Abstract<\/jats:title>\n \n Given a set\n P<\/jats:italic>\n of\n n<\/jats:italic>\n points in\n \n \n $$\\mathbb {R}^d$$<\/jats:tex-math>\n \n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and a positive integer\n \n \n $$k \\le n$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the\n k<\/jats:italic>\n -dispersion problem is that of selecting\n k<\/jats:italic>\n of the given points so that the minimum inter-point distance among them is maximized (under Euclidean distances). Among others, we show the following:\n \n \n \n Given a set\n P<\/jats:italic>\n of\n n<\/jats:italic>\n points in the plane, and a positive integer\n \n \n $$k \\ge 2$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the\n k<\/jats:italic>\n -dispersion problem can be solved by an algorithm running in\n \n \n $$O\\left( n^{k-1} \\log {n}\\right) $$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n time. This extends an earlier result for\n \n \n $$k=3$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , due to Horiyama, Nakano, Saitoh, Suetsugu, Suzuki, Uehara, Uno, and Wasa [20] to arbitrary\n k<\/jats:italic>\n . In particular, it improves on previous running times for small\n k<\/jats:italic>\n .\n <\/jats:p>\n <\/jats:list-item>\n \n \n Given a set\n P<\/jats:italic>\n of\n n<\/jats:italic>\n points in\n \n \n $$\\mathbb {R}^3$$<\/jats:tex-math>\n \n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and a positive integer\n \n \n $$k \\ge 2$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , the\n k<\/jats:italic>\n -dispersion problem can be solved by an algorithm running in\n \n \n $$ {\\left\\{ \\begin{array}{ll} O\\left( n^{k-1} \\log {n}\\right) \\text {time}, & \\text {if } k \\text { is even};\\\\ O\\left( n^{k-1} \\log ^2{n}\\right) \\text {time}, & \\text {if } k \\text { is odd}. \\end{array}\\right. } $$<\/jats:tex-math>\n \n \n \n \n \n \n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mfenced>\n time<\/mml:mtext>\n ,<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n \n \n if<\/mml:mtext>\n \n k<\/mml:mi>\n \n is even<\/mml:mtext>\n \u037e<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n \n k<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mfenced>\n time<\/mml:mtext>\n ,<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n \n \n if<\/mml:mtext>\n \n k<\/mml:mi>\n \n is odd<\/mml:mtext>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>\n For\n \n \n $$k \\ge 4$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , no combinatorial algorithm running in\n \n \n $$o(n^k)$$<\/jats:tex-math>\n \n \n o<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n time was known for this problem.\n <\/jats:p>\n <\/jats:list-item>\n \n \n Let\n P<\/jats:italic>\n be a set of\n n<\/jats:italic>\n random points uniformly distributed in\n \n \n $$[0,1]^2$$<\/jats:tex-math>\n \n \n \n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Then under suitable conditions, a 0.99-approximation for\n k<\/jats:italic>\n -dispersion can be computed in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n ) time with high probability.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n <\/jats:p>","DOI":"10.1007\/s00236-026-00534-1","type":"journal-article","created":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T09:38:52Z","timestamp":1781602732000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A couple of simple algorithms for k-dispersion"],"prefix":"10.1007","volume":"63","author":[{"given":"Ke","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,16]]},"reference":[{"key":"534_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Aronov, B., Sharir, M., Suri, S.: Selecting distances in the plane. In: Proceedings of the 6th Annual Symposium on Computational Geometry, pp. 321\u2013331 (1990)","DOI":"10.1145\/98524.98597"},{"key":"534_CR2","doi-asserted-by":"crossref","unstructured":"Akagi, T., Araki, T., Horiyama, T., Nakano, S.-I., Okamoto, Y., Otachi, Y., Saitoh, T., Uehara, R., Uno, T., Wasa, K.: Exact algorithms for the max-min dispersion problem. In: International Workshop on Frontiers in Algorithmics (FAW 2018). LNCS, vol. 10823. pp. 263\u2013272 (2018)","DOI":"10.1007\/978-3-319-78455-7_20"},{"key":"534_CR3","doi-asserted-by":"crossref","unstructured":"Alman, J., Duan, R., Vassilevska Williams, V., Xu, Y., Xu, Z., Zhou, R.: More asymmetry yields faster matrix multiplication. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 2005\u20132039","DOI":"10.1137\/1.9781611978322.63"},{"issue":"2","key":"534_CR4","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134\u2013151 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"534_CR5","doi-asserted-by":"publisher","first-page":"1824","DOI":"10.1007\/s10878-020-00549-5","volume":"44","author":"T Araki","year":"2022","unstructured":"Araki, T., Nakano, S.: Max-min dispersion on a line. J. Comb. Optim. 44(3), 1824\u20131830 (2022)","journal-title":"J. Comb. Optim."},{"key":"534_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.jalgor.2004.06.009","volume":"62","author":"S Cabello","year":"2007","unstructured":"Cabello, S.: Approximation algorithms for spreading points. J. Algorithms 62, 49\u201373 (2007)","journal-title":"J. Algorithms"},{"issue":"3","key":"534_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1142\/S0218195901000511","volume":"11","author":"TM Chan","year":"2001","unstructured":"Chan, T.M.: On enumerating and selecting distances. Int. J. Comput. Geom. Appl. 11(3), 291\u2013304 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"534_CR8","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1006\/jagm.2000.1145","volume":"38","author":"B Chandra","year":"2001","unstructured":"Chandra, B., Halld\u00f3rsson, M.M.: Approximation algorithms for dispersion problems. J. Algorithms 38(2), 438\u2013465 (2001)","journal-title":"J. Algorithms"},{"key":"534_CR9","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: New techniques for computing order statistics in Euclidean space. In: Proceedings of 1st Annual Symposium on Computational Geometry, pp. 125\u2013134. ACM Press (1985)","DOI":"10.1145\/323233.323251"},{"key":"534_CR10","doi-asserted-by":"crossref","unstructured":"Chen, K., Dumitrescu, A., Lingas, A.: Finding small complete subgraphs efficiently. Preprint arXiv:2308.11146 (2025)","DOI":"10.2139\/ssrn.4729167"},{"key":"534_CR11","doi-asserted-by":"crossref","unstructured":"Dickerson, M.T., Scot Drysdale, R.: Enumerating $$k$$ distances for $$n$$ points in the plane. In: Proceedings of 7th Annual Symposium on Computational Geometry, pp. 234\u2013238 (1991)","DOI":"10.1145\/109648.109674"},{"key":"534_CR12","doi-asserted-by":"crossref","unstructured":"Duan, R., Wu, H., Zhou, R.: Faster matrix multiplication via asymmetric hashing. In: Proceedings of 64th Annual Symposium on Foundations of Computer Science (FOCS 2023), pp. 2129\u20132138. IEEE","DOI":"10.1109\/FOCS57990.2023.00130"},{"key":"534_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00224-011-9331-x","volume":"51","author":"A Dumitrescu","year":"2012","unstructured":"Dumitrescu, A., Jiang, M.: Dispersion in disks. Theory Comput. Syst. 51, 125\u2013142 (2012)","journal-title":"Theory Comput. Syst."},{"key":"534_CR14","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jcta.2015.03.006","volume":"134","author":"A Dumitrescu","year":"2015","unstructured":"Dumitrescu, A., Jiang, M.: Systems of distant representatives in Euclidean space. J. Comb. Theory A 134, 36\u201350 (2015)","journal-title":"J. Comb. Theory A"},{"key":"534_CR15","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Lingas, A.: Finding small complete subgraphs efficiently. In: Proceedings of 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), LNCS 13889, pp. 185\u2013196. Springer, Cham, Switzerland (2023)","DOI":"10.1007\/978-3-031-34347-6_16"},{"issue":"1\u20133","key":"534_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci. 326(1\u20133), 57\u201367 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"534_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21800-2","volume-title":"Lagerungen","author":"L Fejes T\u00f3th","year":"2023","unstructured":"Fejes T\u00f3th, L., Fejes T\u00f3th, G., Kuperberg, W.: Lagerungen. Springer, Cham (2023)"},{"issue":"2","key":"534_CR18","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.dam.2004.02.018","volume":"145","author":"J Fiala","year":"2005","unstructured":"Fiala, J., Kratochv\u00edl, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306\u2013316 (2005)","journal-title":"Discret. Appl. Math."},{"key":"534_CR19","volume-title":"Geometric Approximation Algorithms","author":"S Har-Peled","year":"2011","unstructured":"Har-Peled, S.: Geometric Approximation Algorithms, vol. 173. American Mathematical Society, Providence (2011)"},{"key":"534_CR20","doi-asserted-by":"crossref","unstructured":"Horiyama, T., Nakano, S.-I., Saitoh, T., Suetsugu, K., Suzuki, A., Uehara, R., Uno, T., Wasa, K.: Max-min 3-dispersion problems. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 104(9), 1101\u20131107 (2021)","DOI":"10.1587\/transfun.2020DMP0003"},{"issue":"4","key":"534_CR21","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"534_CR22","doi-asserted-by":"crossref","unstructured":"Le Gall, F., Urrutia, F.: Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In: Proceedings of 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 1029\u20131046. SIAM , New Orleans (2018)","DOI":"10.1137\/1.9781611975031.67"},{"key":"534_CR23","doi-asserted-by":"crossref","unstructured":"Lev-Tov, N., Peleg, D.: Exact algorithms and approximation schemes for base station placement problems. In: Proceedings of the 55th Scandinavian Workshop on Algorithm Theory (SWAT 2002), pp.\u00a090\u201399. Springer (2002)","DOI":"10.1007\/3-540-45471-3_10"},{"issue":"2","key":"534_CR24","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0304-3975(83)90054-3","volume":"23","author":"G Lotti","year":"1983","unstructured":"Lotti, G., Romani, F.: On the asymptotic complexity of rectangular matrix multiplication. Theor. Comput. Sci. 23(2), 171\u2013185 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"534_CR25","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: Proceedings of the 23rd Annual European Symposium on Algorithms, ESA 2015, pp. 865\u2013877. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"534_CR26","doi-asserted-by":"crossref","unstructured":"Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when $$1-1\/d$$ is the best possible exponent for $$d$$-dimensional geometric problems. In: Proceedings of the $$13$$th Annual Symposium on Computational Geometry (SoCG 2010), pp. 67\u201376 (2014)","DOI":"10.1145\/2582112.2582124"},{"key":"534_CR27","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/053","volume-title":"Thirty-Three Miniatures","author":"J Matou\u0161ek","year":"2010","unstructured":"Matou\u0161ek, J.: Thirty-Three Miniatures. American Mathematical Society, Providence (2010)"},{"key":"534_CR28","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"issue":"2","key":"534_CR29","first-page":"415","volume":"26","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 26(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carol."},{"key":"534_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry. Springer, New York (1985)"},{"issue":"2","key":"534_CR31","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00454-001-0029-8","volume":"26","author":"EA Ramos","year":"2001","unstructured":"Ramos, E.A.: An optimal deterministic algorithm for computing the diameter of a three-dimensional point set. Discret. Comput. Geom. 26(2), 233\u2013244 (2001)","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"534_CR32","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1287\/opre.42.2.299","volume":"42","author":"SS Ravi","year":"1994","unstructured":"Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2), 299\u2013310 (1994)","journal-title":"Oper. Res."},{"key":"534_CR33","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Xu, Y., Xu Z., Zhou, R.: New bounds for matrix multiplication: from alpha to omega. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a03792\u20133835. SIAM","DOI":"10.1137\/1.9781611977912.134"},{"issue":"6","key":"534_CR34","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D-W Wang","year":"1988","unstructured":"Wang, D.-W., Kuo, Y.-S.: A study on two geometric location problems. Inf. Process. Lett. 28(6), 281\u2013286 (1988)","journal-title":"Inf. Process. Lett."},{"key":"534_CR35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"issue":"4","key":"534_CR36","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"AC-C Yao","year":"1982","unstructured":"Yao, A.C.-C.: On constructing minimum spanning trees in $$k$$-dimensional spaces and related problems. SIAM J. Comput. 11(4), 721\u2013736 (1982)","journal-title":"SIAM J. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00534-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00534-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00534-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T09:39:19Z","timestamp":1781602759000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00534-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,16]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9]]}},"alternative-id":["534"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00534-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,16]]},"assertion":[{"value":"3 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"20"}}