{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T18:10:01Z","timestamp":1733508601785,"version":"3.30.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"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":["comput. complex."],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00037-024-00254-3","type":"journal-article","created":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T20:27:42Z","timestamp":1720038462000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with a high probability"],"prefix":"10.1007","volume":"33","author":[{"given":"M.","family":"Rada","sequence":"first","affiliation":[]},{"given":"M.","family":"\u010cern\u00fd","sequence":"additional","affiliation":[]},{"given":"O.","family":"Sokol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,3]]},"reference":[{"key":"254_CR1","doi-asserted-by":"crossref","unstructured":"Dennis Amelunxen & Martin Lotz (2017). Average-case complexity without the black swans. Journal of Complexity 41, 82\u2013101","DOI":"10.1016\/j.jco.2016.12.002"},{"key":"254_CR2","doi-asserted-by":"crossref","unstructured":"Jarom\u00edr Antoch, Miroslav Brzezina & Rafaelle Miele (2010). A Note on Variability of Interval Data. Computational Statistics 25(1), 143\u2013153","DOI":"10.1007\/s00180-009-0166-8"},{"key":"254_CR3","doi-asserted-by":"crossref","unstructured":"Rene Beier & Berthold V\u00f6cking (2004). Random knapsack in expected polynomial time. Journal of Computer and System Sciences 69(3), 306\u2013329.","DOI":"10.1016\/j.jcss.2004.04.004"},{"key":"254_CR4","doi-asserted-by":"crossref","unstructured":"Rene Beier & Berthold V\u00f6cking (2006). Typical Properties of Winners and Losers in Discrete Optimization. SIAM Journal on Computing 35(4), 855\u2013881","DOI":"10.1137\/S0097539705447268"},{"key":"254_CR5","doi-asserted-by":"crossref","unstructured":"K. H. Borgwardt (1982). The Average Number of Pivot Steps Required by the Simplex-Method Is Polynomial. Zeitschrift f\u00fcr Operations Research 26(1), 157\u2013177","DOI":"10.1007\/BF01917108"},{"key":"254_CR6","doi-asserted-by":"crossref","unstructured":"Michal \u010cern\u00fd & Milan Hlad\u00edk (2014). The Complexity of Computation and Approximation of the T-Ratio over One-Dimensional Interval Data. Computational Statistics & Data Analysis 80, 26\u201343","DOI":"10.1016\/j.csda.2014.06.007"},{"key":"254_CR7","doi-asserted-by":"crossref","unstructured":"Scott Ferson, Lev Ginzburg, Vladik Kreinovich, Luc Longpr\u00e9 & Monica Aviles (2005). Exact Bounds on Finite Populations of Interval Data. Reliable Computing 11(3), 207\u2013233","DOI":"10.1007\/s11155-005-3616-1"},{"key":"254_CR8","doi-asserted-by":"crossref","unstructured":"Michel X Goemans & David P Williamson (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) 42(6), 1115\u20131145.","DOI":"10.1145\/227683.227684"},{"key":"254_CR9","unstructured":"Vladik Kreinovich, Anatoly Lakeyev, Ji\u0159\u00ed Rohn & Patrick Kahl (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, volume 10 of Applied Optimization. Springer US, Boston, MA. ISBN 978-1-4419-4785-7 978-1-4757-2793-7."},{"key":"254_CR10","unstructured":"Charles F. Manski (2003). Partial Identification of Probability Distributions. Springer, Berlin."},{"key":"254_CR11","doi-asserted-by":"crossref","unstructured":"George L Nemhauser & Zev Ullmann (1969). Discrete dynamic programming and capital allocation. Management Science 15(9), 494\u2013505.","DOI":"10.1287\/mnsc.15.9.494"},{"key":"254_CR12","doi-asserted-by":"crossref","unstructured":"Yu Nesterov (1998). Semidefinite relaxation and nonconvex quadratic optimization. Optimization methods and software 9(1-3), 141\u2013160.","DOI":"10.1080\/10556789808805690"},{"key":"254_CR13","doi-asserted-by":"crossref","unstructured":"Hung T. Nguyen, Vladik Kreinovich, Berlin Wu & Gang Xiang (2012). Computing Statistics under Interval and Fuzzy Uncertainty. Studies in Computational Intelligence 393.","DOI":"10.1007\/978-3-642-24905-1"},{"key":"254_CR14","doi-asserted-by":"crossref","unstructured":"Mathew Penrose (2003). Random Geometric Graphs. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"254_CR15","doi-asserted-by":"crossref","unstructured":"Daniel A. Spielman & Shang-Hua Teng (2004). Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Journal of the ACM 51(3), 385\u2013463","DOI":"10.1145\/990308.990310"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00254-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00254-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00254-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T03:06:18Z","timestamp":1733454378000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00254-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,3]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["254"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00254-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2024,7,3]]},"assertion":[{"value":"7 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}