{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,26]],"date-time":"2026-04-26T12:38:20Z","timestamp":1777207100821,"version":"3.51.4"},"reference-count":19,"publisher":"Walter de Gruyter GmbH","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we introduce a new algorithm for estimating the lower bounds for the star discrepancy of any arbitrary point sets in <jats:inline-formula>\n                     <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:msup>\n                              <m:mrow>\n                                 <m:mo stretchy=\"false\">[<\/m:mo>\n                                 <m:mn>0<\/m:mn>\n                                 <m:mo>,<\/m:mo>\n                                 <m:mn>1<\/m:mn>\n                                 <m:mo stretchy=\"false\">]<\/m:mo>\n                              <\/m:mrow>\n                              <m:mi>s<\/m:mi>\n                           <\/m:msup>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_mcma-2023-2005_ineq_0001.png\"\/>\n                        <jats:tex-math>[0,1]^{s}<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>.\nComputing the exact star discrepancy is known to be an NP-hard problem, so we have been looking for effective approximation algorithms.\nThe star discrepancy can be thought of as the maximum of a function called the local discrepancy, and we will develop approximation algorithms to maximize this function.\nOur algorithm is analogous to the random walk algorithm described in one of our previous papers [M. Alsolami and M. Mascagni, A random walk algorithm to estimate a lower bound of the star discrepancy, <jats:italic>Monte Carlo Methods Appl.<\/jats:italic>\n                  <jats:bold>28<\/jats:bold> (2022), 4, 341\u2013348.].\nWe add a statistical technique to the random walk algorithm by implementing the Metropolis algorithm in random walks on each chosen dimension to accept or reject this movement.\nWe call this Metropolis random walk algorithm.\nIn comparison to all previously known techniques, our new algorithm is superior, especially in high dimensions.\nAlso, it can quickly determine the precise value of the star discrepancy in most of our data sets of various sizes and dimensions, or at least the lower bounds of the star discrepancy.<\/jats:p>","DOI":"10.1515\/mcma-2023-2005","type":"journal-article","created":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T16:50:06Z","timestamp":1683737406000},"page":"161-171","source":"Crossref","is-referenced-by-count":1,"title":["A Metropolis random walk algorithm to estimate a lower bound of the star discrepancy"],"prefix":"10.1515","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9131-814X","authenticated-orcid":false,"given":"Maryam","family":"Alsolami","sequence":"first","affiliation":[{"name":"Department of Computer Science , Florida State University , Tallahassee , FL 32306-4530 , USA ; and College of Computers and Information Systems, Umm Al-Qura University, Kingdom of Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3058-4580","authenticated-orcid":false,"given":"Michael","family":"Mascagni","sequence":"additional","affiliation":[{"name":"Department of Computer Science , Florida State University , Tallahassee , FL 32306-4530 ; and National Institute of Standards & Technology, ITL, Gaithersburg, MD 20899-8910 , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"key":"2023053118460960971_j_mcma-2023-2005_ref_001","doi-asserted-by":"crossref","unstructured":"M. Alsolami and M. Mascagni,\nA random walk algorithm to estimate a lower bound of the star discrepancy,\nMonte Carlo Methods Appl. 28 (2022), no. 4, 341\u2013348.","DOI":"10.1515\/mcma-2022-2125"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_002","doi-asserted-by":"crossref","unstructured":"G. Bhanot,\nThe Metropolis algorithm,\nRep. Progr. Phys. 51 (1988), no. 3, 429\u2013457.","DOI":"10.1088\/0034-4885\/51\/3\/003"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_003","doi-asserted-by":"crossref","unstructured":"J. Dick and F. Pillichshammer,\nDigital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration,\nCambridge University, Cambridge, 2010.","DOI":"10.1017\/CBO9780511761188"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_004","doi-asserted-by":"crossref","unstructured":"C. Doerr, M. Gnewuch and M. Wahlstr\u00f6m,\nCalculation of discrepancy measures and applications,\nA Panorama of Discrepancy Theory,\nLecture Notes in Math. 2107,\nSpringer, Cham (2014), 621\u2013678.","DOI":"10.1007\/978-3-319-04696-9_10"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_005","doi-asserted-by":"crossref","unstructured":"C. Doerr and F.-M. De Rainville,\nConstructing low star discrepancy point sets with genetic algorithms,\nProceedings of the 15th Annual Conference on Genetic and Evolutionary Computation,\nAssociation for Computing Machinery, New York (2013), 789\u2013796.","DOI":"10.1145\/2463372.2463469"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_006","doi-asserted-by":"crossref","unstructured":"M. Gnewuch, A. Srivastav and C. Winzen,\nFinding optimal volume subintervals with \ud835\udc58-points and calculating the star discrepancy are NP-hard problems,\nJ. Complexity 25 (2009), no. 2, 115\u2013127.","DOI":"10.1016\/j.jco.2008.10.001"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_007","doi-asserted-by":"crossref","unstructured":"M. Gnewuch, M. Wahlstr\u00f6m and C. Winzen,\nA new randomized algorithm to approximate the star discrepancy based on threshold accepting,\nSIAM J. Numer. Anal. 50 (2012), no. 2, 781\u2013807.","DOI":"10.1137\/110833865"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_008","unstructured":"Y. Li,\nThe computational measure of uniformity,\nMaster\u2019s thesis, Florida State University, 2000."},{"key":"2023053118460960971_j_mcma-2023-2005_ref_009","doi-asserted-by":"crossref","unstructured":"N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller and E. Teller,\nEquation of state calculations by fast computing machines,\nJ. Chem. Phys. 21 (1953), no. 6, 1087\u20131092.","DOI":"10.1063\/1.1699114"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_010","doi-asserted-by":"crossref","unstructured":"W. J. Morokoff and R. E. Caflisch,\nQuasi-random sequences and their discrepancies,\nSIAM J. Sci. Comput. 15 (1994), no. 6, 1251\u20131279.","DOI":"10.1137\/0915077"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_011","doi-asserted-by":"crossref","unstructured":"W. J. Morokoff and R. E. Caflisch,\nQuasi-Monte Carlo integration,\nJ. Comput. Phys. 122 (1995), no. 2, 218\u2013230.","DOI":"10.1006\/jcph.1995.1209"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_012","doi-asserted-by":"crossref","unstructured":"H. Niederreiter,\nDiscrepancy and convex programming,\nAnn. Mat. Pura Appl. (4) 93 (1972), 89\u201397.","DOI":"10.1007\/BF02412017"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_013","doi-asserted-by":"crossref","unstructured":"H. Niederreiter,\nQuasi-Monte Carlo methods and pseudo-random numbers,\nBull. Amer. Math. Soc. 84 (1978), no. 6, 957\u20131041.","DOI":"10.1090\/S0002-9904-1978-14532-7"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_014","doi-asserted-by":"crossref","unstructured":"G. \u00d6kten, M. Shah and Y. Goncharov,\nRandom and deterministic digit permutations of the Halton sequence,\nMonte Carlo and Quasi-Monte Carlo Methods 2010,\nSpringer Proc. Math. Stat. 23,\nSpringer, Heidelberg (2012), 609\u2013622.","DOI":"10.1007\/978-3-642-27440-4_35"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_015","unstructured":"M. Shah,\nQuasi-Monte Carlo and genetic algorithms with applications to endogenous mortgage rate computation,\nPh.D. thesis, The Florida State University, 2008."},{"key":"2023053118460960971_j_mcma-2023-2005_ref_016","doi-asserted-by":"crossref","unstructured":"M. Shah,\nA genetic algorithm approach to estimate lower bounds of the star discrepancy,\nMonte Carlo Methods Appl. 16 (2010), no. 3\u20134, 379\u2013398.","DOI":"10.1515\/mcma.2010.014"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_017","doi-asserted-by":"crossref","unstructured":"E. Thi\u00e9mard,\nAn algorithm to compute bounds for the star discrepancy,\nJ. Complexity 17 (2001), no. 4, 850\u2013880.","DOI":"10.1006\/jcom.2001.0600"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_018","doi-asserted-by":"crossref","unstructured":"E. Thi\u00e9mard,\nOptimal volume subintervals with \ud835\udc58 points and star discrepancy via integer programming,\nMath. Methods Oper. Res. 54 (2001), no. 1, 21\u201345.","DOI":"10.1007\/s001860100141"},{"key":"2023053118460960971_j_mcma-2023-2005_ref_019","doi-asserted-by":"crossref","unstructured":"P. Winker and K.-T. Fang,\nApplication of threshold-accepting to the evaluation of the discrepancy of a set of points,\nSIAM J. Numer. Anal. 34 (1997), no. 5, 2028\u20132042.","DOI":"10.1137\/S0036142995286076"}],"container-title":["Monte Carlo Methods and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2005\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2005\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T18:46:19Z","timestamp":1685558779000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/mcma-2023-2005\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":19,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,5,10]]},"published-print":{"date-parts":[[2023,6,1]]}},"alternative-id":["10.1515\/mcma-2023-2005"],"URL":"https:\/\/doi.org\/10.1515\/mcma-2023-2005","relation":{},"ISSN":["0929-9629","1569-3961"],"issn-type":[{"value":"0929-9629","type":"print"},{"value":"1569-3961","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,10]]}}}