{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:50:59Z","timestamp":1761648659056,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,25]],"date-time":"2019-06-25T00:00:00Z","timestamp":1561420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,25]]},"DOI":"10.1145\/3294052.3319691","type":"proceedings-article","created":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T12:56:45Z","timestamp":1560776205000},"page":"200-217","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model"],"prefix":"10.1145","author":[{"given":"Piotr","family":"Indyk","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Ali","family":"Vakilian","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,25]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/2487575.2487636"},{"key":"e_1_3_2_1_2_1","volume-title":"Submodular secretary problem with shortlists. arXiv preprint arXiv:1809.05082","author":"Agrawal S.","year":"2018","unstructured":"S. Agrawal , M. Shadravan , and C. Stein . Submodular secretary problem with shortlists. arXiv preprint arXiv:1809.05082 , 2018 . To appear in ITCS 2019. S. Agrawal, M. Shadravan, and C. Stein. Submodular secretary problem with shortlists. arXiv preprint arXiv:1809.05082, 2018. To appear in ITCS 2019."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.5555\/2095116.2095156"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1145\/2213556.2213560"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1006\/jcss.1997.1545"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/3034786.3056116"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/2897518.2897576"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.5555\/2884435.2884528"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/2623330.2623637"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1016\/j.jcss.2003.11.006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.5555\/646978.711822"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/3087556.3087585"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.5555\/3174304.3175461"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1145\/3034786.3034798"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/2897518.2897558"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1109\/CCC.2003.1214414"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.5555\/2884435.2884529"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.5555\/646255.684566"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/1772690.1772715"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.5555\/2884435.2884527"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1007\/978-3-662-45174-8_33"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1007\/978-3-662-43948-7_38"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_24_1","first-page":"505","volume-title":"26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26--28, 2009, Freiburg","author":"Gronemeier A.","year":"2009","unstructured":"A. Gronemeier . Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness . In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26--28, 2009, Freiburg , Germany, Proceedings , pages 505 -- 516 , 2009 . A. Gronemeier. Asymptotically optimal lower bounds on the nih-multi-party information complexity of the and-function and disjointness. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26--28, 2009, Freiburg, Germany, Proceedings, pages 505--516, 2009."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1145\/2745754.2745763"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1145\/2902251.2902287"},{"key":"e_1_3_2_1_27_1","first-page":"198","volume-title":"Fractional set cover in the streaming model. Approximation, Randomization, and Combinatorial Optimization (APPROX\/RANDOM)","author":"Indyk P.","year":"2017","unstructured":"P. Indyk , S. Mahabadi , R. Rubinfeld , J. Ullman , A. Vakilian , and A. Yodpinyanee . Fractional set cover in the streaming model. Approximation, Randomization, and Combinatorial Optimization (APPROX\/RANDOM) , pages 198 -- 217 , 2017 . P. Indyk, S. Mahabadi, R. Rubinfeld, J. Ullman, A. Vakilian, and A. Yodpinyanee. Fractional set cover in the streaming model. Approximation, Randomization, and Combinatorial Optimization (APPROX\/RANDOM), pages 198--217, 2017."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.5555\/3174304.3175463"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1145\/1060590.1060621"},{"key":"e_1_3_2_1_30_1","volume-title":"Revisiting norm estimation in data streams. arXiv preprint arXiv:0811.3648","author":"Kane D. M.","year":"2008","unstructured":"D. M. Kane , J. Nelson , and D. P. Woodruff . Revisiting norm estimation in data streams. arXiv preprint arXiv:0811.3648 , 2008 . D. M. Kane, J. Nelson, and D. P. Woodruff. Revisiting norm estimation in data streams. arXiv preprint arXiv:0811.3648, 2008."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1145\/1807085.1807094"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1137\/141002281"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_3_2_1_34_1","first-page":"1","volume-title":"20th International Conference on Database Theory (ICDT)","author":"McGregor A.","year":"2017","unstructured":"A. McGregor and H. T. Vu . Better streaming algorithms for the maximum coverage problem . In 20th International Conference on Database Theory (ICDT) , pages 22: 1 -- 22 :18, 2017 . A. McGregor and H. T. Vu. Better streaming algorithms for the maximum coverage problem. In 20th International Conference on Database Theory (ICDT), pages 22:1--22:18, 2017."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_36_1","first-page":"3826","volume-title":"International Conference on Machine Learning (ICML)","author":"Norouzi-Fard A.","year":"2018","unstructured":"A. Norouzi-Fard , J. Tarnawski , S. Mitrovic , A. Zandieh , A. Mousavifar , and O. Svensson . Beyond 1\/2-approximation for submodular maximization on massive data streams . In International Conference on Machine Learning (ICML) , pages 3826 -- 3835 , 2018 . A. Norouzi-Fard, J. Tarnawski, S. Mitrovic, A. Zandieh, A. Mousavifar, and O. Svensson. Beyond 1\/2-approximation for submodular maximization on massive data streams. In International Conference on Machine Learning (ICML), pages 3826--3835, 2018."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1137\/1.9781611972795.60"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1137\/S089548019223872X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1137\/100800774"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.5555\/2464831"}],"event":{"sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"acronym":"SIGMOD\/PODS '19","name":"SIGMOD\/PODS '19: International Conference on Management of Data","location":"Amsterdam Netherlands"},"container-title":["Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3294052.3319691","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3294052.3319691","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3294052.3319691","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:48Z","timestamp":1750208508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3294052.3319691"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,25]]},"references-count":40,"alternative-id":["10.1145\/3294052.3319691","10.1145\/3294052"],"URL":"https:\/\/doi.org\/10.1145\/3294052.3319691","relation":{},"subject":[],"published":{"date-parts":[[2019,6,25]]},"assertion":[{"value":"2019-06-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}