{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:04Z","timestamp":1740109324945,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2364"],"award-info":[{"award-number":["N00014-18-1-2364"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001658","name":"Minerva Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001658","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["#1086\/18"],"award-info":[{"award-number":["#1086\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00453-022-00988-y","type":"journal-article","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T10:03:51Z","timestamp":1656065031000},"page":"2926-2953","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Almost-Smooth Histograms and Sliding-Window Graph Algorithms"],"prefix":"10.1007","volume":"84","author":[{"given":"Robert","family":"Krauthgamer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8939-3626","authenticated-orcid":false,"given":"David","family":"Reitblat","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"988_CR1","doi-asserted-by":"publisher","unstructured":"Aggarwal, C.: Data Streams: Models and Algorithms, volume\u00a031 of Advances in Database Systems. Springer-Verlag, (01 2007). https:\/\/doi.org\/10.1007\/978-0-387-47534-9","DOI":"10.1007\/978-0-387-47534-9"},{"key":"988_CR2","doi-asserted-by":"publisher","unstructured":"B\u0142asiok, J., Braverman, V., Chestnut, S.R., Krauthgamer, R., Yang, L.F.: Streaming Symmetric Norms Via Measure Concentration. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, 716\u2013729 (2017). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/3055399.3055424","DOI":"10.1145\/3055399.3055424"},{"key":"988_CR3","doi-asserted-by":"publisher","unstructured":"Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and Issues in Data Stream Systems. In: Proceedings of the Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS \u201902, pp. 1\u201316. ACM, (2002). https:\/\/doi.org\/10.1145\/543613.543615","DOI":"10.1145\/543613.543615"},{"key":"988_CR4","doi-asserted-by":"publisher","unstructured":"Bhatia, R.: Matrix Analysis, volume 169 of Graduate texts in mathematics. Springer-Verlag, New York, (1997). https:\/\/doi.org\/10.1007\/978-1-4612-0653-8","DOI":"10.1007\/978-1-4612-0653-8"},{"key":"988_CR5","unstructured":"Braverman, V., Krauthgamer, R., Krishnan, A., Sinoff, R.: Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. In ICML, (2020)"},{"key":"988_CR6","doi-asserted-by":"publisher","unstructured":"Braverman, V., Ostrovsky, R.: Smooth Histograms for Sliding Windows. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201907, pp. 283\u2013293. IEEE Computer Society, (2007). https:\/\/doi.org\/10.1109\/FOCS.2007.63","DOI":"10.1109\/FOCS.2007.63"},{"key":"988_CR7","doi-asserted-by":"publisher","unstructured":"Bury, M., Schwiegelshohn, C.: Sublinear Estimation of Weighted Matchings in Dynamic Data Streams. In: Algorithms - ESA, pp. 263\u2013274. Springer Berlin Heidelberg, (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_23","DOI":"10.1007\/978-3-662-48350-3_23"},{"key":"988_CR8","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization Via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201916, pp. 1326\u20131344. Society for Industrial and Applied Mathematics, (2016). Available from: http:\/\/dl.acm.org\/citation.cfm?id=2884435.2884527","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"988_CR9","doi-asserted-by":"publisher","unstructured":"Cormode, G., Jowhari, H., Monemizadeh, M., Muthukrishnan, S.: The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In: 25th Annual European Symposium on Algorithms (ESA), volume\u00a087 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 29:1\u201329:15, (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.29","DOI":"10.4230\/LIPIcs.ESA.2017.29"},{"key":"988_CR10","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: Matchings, matroids, and more. In: Lee, J., Vygen, J. (eds.) Integer Programming and Combinatorial Optimization. pp. 210\u2013221. Springer International Publishing, Cham (2014)","DOI":"10.1007\/978-3-319-07557-0_18"},{"key":"988_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-40450-4_29","volume":"2013","author":"MS Crouch","year":"2013","unstructured":"Crouch, M.S., McGregor, A., Stubbs, D.: Dynamic Graphs in the Sliding-Window Model. In Algorithms - ESA 2013, 337\u2013348 (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_29","journal-title":"In Algorithms - ESA"},{"issue":"6","key":"988_CR12","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining Stream Statistics Over Sliding Windows. SIAM Journal on Computing 31(6), 1794\u20131813 (2002). https:\/\/doi.org\/10.1137\/S0097539701398363","journal-title":"SIAM Journal on Computing"},{"key":"988_CR13","doi-asserted-by":"publisher","unstructured":"Esfandiari, H., Hajiaghayi, M.T., Liaghat, V., Monemizadeh, M., Onak, K.: Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond. ACM Trans. Algorithms, 14(4):48:1\u201348:23, (August 2018). https:\/\/doi.org\/10.1145\/3230819","DOI":"10.1145\/3230819"},{"key":"988_CR14","doi-asserted-by":"publisher","unstructured":"Feige, U., Jozeph, S.: Separation between Estimation and Approximation. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS \u201915, pp. 271\u2013276. ACM, (2015). https:\/\/doi.org\/10.1145\/2688073.2688101","DOI":"10.1145\/2688073.2688101"},{"issue":"2","key":"988_CR15","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On Graph Problems in a Semi-Streaming Model. Theor. Comput. Sci. 348(2), 207\u2013216 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.013","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"988_CR16","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/BF01585521","volume":"7","author":"AM Frieze","year":"1974","unstructured":"Frieze, A.M.: A Cost Function Property for Plant Location Problems. Math. Program. 7(1), 245\u2013248 (1974). https:\/\/doi.org\/10.1007\/BF01585521","journal-title":"Math. Program."},{"issue":"1","key":"988_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0166-218X(98)00007-9","volume":"84","author":"R Grossi","year":"1998","unstructured":"Grossi, R., Lodi, E.: Simple Planar Graph Partition into Three Forests. Discret. Appl. Math. 84(1), 121\u2013132 (1998). https:\/\/doi.org\/10.1016\/S0166-218X(98)00007-9","journal-title":"Discret. Appl. Math."},{"key":"988_CR18","doi-asserted-by":"publisher","unstructured":"Krause, A., Golovin, D.: Submodular Function Maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems, pp. 71-104. Cambridge University Press, (2014). https:\/\/doi.org\/10.1017\/CBO9781139177801.004","DOI":"10.1017\/CBO9781139177801.004"},{"issue":"1","key":"988_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph Stream Algorithms: A survey. SIGMOD Rec. 43(1), 9\u201320 (2014). https:\/\/doi.org\/10.1145\/2627692.2627694","journal-title":"SIGMOD Rec."},{"issue":"2","key":"988_CR20","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data Streams: Algorithms and Applications. Found. Trends Theor. Comput. Sci. 1(2), 117\u2013236 (2005). https:\/\/doi.org\/10.1561\/0400000002","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"988_CR21","doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S.: Planar Matching in Streams Revisited. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2016), vol. 60 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 17:1\u201317:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2016). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2016.17","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2016.17"},{"key":"988_CR22","doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S.: A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In: 1st Symposium on Simplicity in Algorithms (SOSA), vol.\u00a061 of OpenAccess Series in Informatics (OASIcs), pp. 14:1\u201314:4. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.14","DOI":"10.4230\/OASIcs.SOSA.2018.14"},{"issue":"7","key":"988_CR23","doi-asserted-by":"publisher","first-page":"1595","DOI":"10.1007\/s00224-018-9878-x","volume":"63","author":"A McGregor","year":"2019","unstructured":"McGregor, A., Vu, H.T.: Better Streaming Algorithms for the Maximum Coverage Problem. Theory of Computing Systems 63(7), 1595\u20131619 (2019). https:\/\/doi.org\/10.1007\/s00224-018-9878-x","journal-title":"Theory of Computing Systems"},{"key":"988_CR24","unstructured":"van Handel, O.: Vertex Cover Approximation in Data Streams. Master\u2019s Thesis, Weizmann Institute of Science, (2016). Available from: http:\/\/www.wisdom.weizmann.ac.il\/~robi\/files\/OtnielVanHandel-MScThesis-2017_01.pdf"},{"key":"988_CR25","doi-asserted-by":"publisher","unstructured":"Woodruff, D.P., Zhou, S.: Tight Bounds for Adversarially Robust Streams and Sliding Windows Via Difference Estimators. In: 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), pp. 1183\u20131196, (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00116","DOI":"10.1109\/FOCS52979.2021.00116"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00988-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00988-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00988-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T14:19:25Z","timestamp":1664547565000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00988-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":25,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["988"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00988-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,6,24]]},"assertion":[{"value":"20 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}