[{"date_created":"2024-10-13T22:01:50Z","date_updated":"2026-10-21T08:04:40Z","file":[{"file_size":873561,"access_level":"open_access","file_id":"18454","content_type":"application/pdf","checksum":"8e8c0b13049f11bb0133dfac22e32718","file_name":"2024_LIPICs_DuprelaTour.pdf","creator":"dernst","success":1,"date_updated":"2024-10-21T09:41:48Z","date_created":"2024-10-21T09:41:48Z","relation":"main_file"}],"ddc":["000"],"OA_place":"publisher","language":[{"iso":"eng"}],"isi":1,"status":"public","has_accepted_license":"1","file_date_updated":"2024-10-21T09:41:48Z","quality_controlled":"1","publication_status":"published","alternative_title":["LIPIcs"],"type":"conference","author":[{"last_name":"La Tour","first_name":"Max Dupré","full_name":"La Tour, Max Dupré"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Saulpic, David","first_name":"David","last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"ama":"La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal update time. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>","ieee":"M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset in near-optimal update time,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308.","apa":"La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Fully dynamic k-means coreset in near-optimal update time. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>","chicago":"La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>.","mla":"La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>.","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100."},"month":"09","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes","conference":{"start_date":"2024-09-02","name":"ESA: European Symposium on Algorithms","end_date":"2024-09-04","location":"London, United Kingdom"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"external_id":{"arxiv":["2406.19926"],"isi":["001545622400100"]},"supplementarymaterial":"no","publication":"32nd Annual European Symposium on Algorithms","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"volume":308,"ec_funded":1,"abstract":[{"lang":"eng","text":"We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd)."}],"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic: Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).","OA_type":"gold","day":"23","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.100","doi":"10.4230/LIPIcs.ESA.2024.100","year":"2024","das_tickbox":"0","date_published":"2024-09-23T00:00:00Z","researchdata_availability":"no","article_number":"100","intvolume":"       308","scopus_import":"1","title":"Fully dynamic k-means coreset in near-optimal update time","_id":"18308","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"corr_author":"1","department":[{"_id":"MoHe"}],"oa":1},{"date_published":"2024-09-01T00:00:00Z","scopus_import":"1","title":"Connectivity oracles for predictable vertex failures","article_number":"72","intvolume":"       308","researchdata_availability":"no","_id":"18309","department":[{"_id":"MoHe"}],"oa":1,"corr_author":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"publication":"32nd Annual European Symposium on Algorithms","supplementarymaterial":"no","external_id":{"arxiv":["2312.08489"],"isi":["001545622400072"]},"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"text":"The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC'10; Long-Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions.","lang":"eng"}],"volume":308,"das_tickbox":"0","year":"2024","doi":"10.4230/LIPIcs.ESA.2024.72","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.72","OA_type":"gold","acknowledgement":"Part of this work was done when Evangelos Kosinas was at University of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n","day":"01","quality_controlled":"1","file_date_updated":"2024-10-21T10:03:48Z","author":[{"first_name":"Bingbing","full_name":"Hu, Bingbing","last_name":"Hu"},{"id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas","first_name":"Evangelos","full_name":"Kosinas, Evangelos"},{"last_name":"Polak","first_name":"Adam","full_name":"Polak, Adam"}],"type":"conference","publication_status":"published","alternative_title":["LIPIcs"],"month":"09","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"short":"B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 72.","mla":"Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>.","chicago":"Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles for Predictable Vertex Failures.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>.","apa":"Hu, B., Kosinas, E., &#38; Polak, A. (2024). Connectivity oracles for predictable vertex failures. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>","ieee":"B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex failures,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308.","ama":"Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>"},"conference":{"location":"London, United Kingdom","name":"ESA: European Symposium on Algorithms","start_date":"2024-09-02","end_date":"2024-09-04"},"article_processing_charge":"Yes","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-21T08:04:56Z","date_created":"2024-10-13T22:01:50Z","file":[{"content_type":"application/pdf","checksum":"ab1f2f9161549a8763eda15db40e022c","success":1,"creator":"dernst","file_name":"2024_LIPICs_Hu.pdf","relation":"main_file","date_created":"2024-10-21T10:03:48Z","date_updated":"2024-10-21T10:03:48Z","access_level":"open_access","file_size":853914,"file_id":"18455"}],"isi":1,"ddc":["000"],"OA_place":"publisher","language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public"}]