[{"type":"conference","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","text":"In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem.\r\n\r\nWe present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11832","intvolume":" 87","title":"Dynamic clustering to minimize the sum of radii","status":"public","oa_version":"Published Version","scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"apa":"Henzinger, M. H., Leniowski, D., & Mathieu, C. (2017). Dynamic clustering to minimize the sum of radii. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.48","ieee":"M. H. Henzinger, D. Leniowski, and C. Mathieu, “Dynamic clustering to minimize the sum of radii,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","ista":"Henzinger MH, Leniowski D, Mathieu C. 2017. Dynamic clustering to minimize the sum of radii. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 48.","ama":"Henzinger MH, Leniowski D, Mathieu C. Dynamic clustering to minimize the sum of radii. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.48","chicago":"Henzinger, Monika H, Dariusz Leniowski, and Claire Mathieu. “Dynamic Clustering to Minimize the Sum of Radii.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.48.","short":"M.H. Henzinger, D. Leniowski, C. Mathieu, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Henzinger, Monika H., et al. “Dynamic Clustering to Minimize the Sum of Radii.” 25th Annual European Symposium on Algorithms, vol. 87, 48, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.48."},"publication":"25th Annual European Symposium on Algorithms","date_published":"2017-09-01T00:00:00Z","article_number":"48","extern":"1","year":"2017","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Leniowski, Dariusz","last_name":"Leniowski","first_name":"Dariusz"},{"first_name":"Claire","last_name":"Mathieu","full_name":"Mathieu, Claire"}],"volume":87,"date_updated":"2023-02-16T11:54:12Z","date_created":"2022-08-12T09:58:46Z","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"month":"09","external_id":{"arxiv":["1707.02577"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.4230/LIPICS.ESA.2017.48","open_access":"1"}],"quality_controlled":"1","doi":"10.4230/LIPICS.ESA.2017.48","conference":{"end_date":"2017-09-06","location":"Vienna, Austria","start_date":"2017-09-04","name":"ESA: Annual European Symposium on Algorithms"},"language":[{"iso":"eng"}]},{"abstract":[{"lang":"eng","text":"We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1).\r\n\r\nWe bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊."}],"type":"conference","oa_version":"Preprint","_id":"11874","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2017-01-01T00:00:00Z","citation":{"ama":"Bhattacharya S, Henzinger MH, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:10.1137/1.9781611974782.30","ista":"Bhattacharya S, Henzinger MH, Nanongkai D. 2017. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 0, 470–489.","apa":"Bhattacharya, S., Henzinger, M. H., & Nanongkai, D. (2017). Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 0, pp. 470–489). Barcelona, Spain: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.30","ieee":"S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, vol. 0, pp. 470–489.","mla":"Bhattacharya, Sayan, et al. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” 28th Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 0, Society for Industrial and Applied Mathematics, 2017, pp. 470–89, doi:10.1137/1.9781611974782.30.","short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 470–489.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in o(Log3 n) Worst Case Update Time.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 0:470–89. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.30."},"publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","page":"470 - 489","extern":"1","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"volume":"0","date_created":"2022-08-16T12:28:27Z","date_updated":"2023-02-17T11:54:22Z","year":"2017","publisher":"Society for Industrial and Applied Mathematics","publication_status":"published","publication_identifier":{"eisbn":["978-161197478-2"]},"month":"01","doi":"10.1137/1.9781611974782.30","conference":{"end_date":"2017-01-19","location":"Barcelona, Spain","start_date":"2017-01-16","name":"SODA: Symposium on Discrete Algorithms"},"language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1704.02844"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.02844"}],"quality_controlled":"1"},{"publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","year":"2017","date_created":"2022-08-16T12:20:59Z","date_updated":"2023-02-21T16:32:01Z","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Rao, Satish","first_name":"Satish","last_name":"Rao"},{"first_name":"Di","last_name":"Wang","full_name":"Wang, Di"}],"related_material":{"record":[{"id":"11889","relation":"earlier_version","status":"public"}]},"extern":"1","quality_controlled":"1","oa":1,"external_id":{"arxiv":["1704.01254"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.01254"}],"language":[{"iso":"eng"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2017-01-19","start_date":"2017-01-16","location":"Barcelona, Spain"},"doi":"10.1137/1.9781611974782.125","month":"01","publication_identifier":{"eisbn":["978-161197478-2"]},"title":"Local flow partitioning for faster edge connectivity","status":"public","_id":"11873","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","type":"conference","abstract":[{"text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest.","lang":"eng"}],"page":"1919-1938","publication":"28th Annual ACM-SIAM Symposium on Discrete Algorithms","citation":{"apa":"Henzinger, M. H., Rao, S., & Wang, D. (2017). Local flow partitioning for faster edge connectivity. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1919–1938). Barcelona, Spain: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.125","ieee":"M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 1919–1938.","ista":"Henzinger MH, Rao S, Wang D. 2017. Local flow partitioning for faster edge connectivity. 28th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1919–1938.","ama":"Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2017:1919-1938. doi:10.1137/1.9781611974782.125","chicago":"Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” In 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 1919–38. Society for Industrial and Applied Mathematics, 2017. https://doi.org/10.1137/1.9781611974782.125.","short":"M.H. Henzinger, S. Rao, D. Wang, in:, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–1938.","mla":"Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.” 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, pp. 1919–38, doi:10.1137/1.9781611974782.125."},"date_published":"2017-01-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No"},{"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2017","date_created":"2022-08-12T09:27:11Z","date_updated":"2023-02-21T16:32:16Z","volume":87,"author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Peng","first_name":"Pan","full_name":"Peng, Pan"}],"related_material":{"record":[{"id":"11894","status":"public","relation":"later_version"}]},"article_number":"44","extern":"1","quality_controlled":"1","oa":1,"external_id":{"arxiv":["1702.01136"]},"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2017.44","open_access":"1"}],"language":[{"iso":"eng"}],"conference":{"name":"ESA: Annual European Symposium on Algorithms","end_date":"2017-09-06","location":"Vienna, Austria","start_date":"2017-09-04"},"doi":"10.4230/LIPICS.ESA.2017.44","month":"09","publication_identifier":{"isbn":["978-3-95977-049-1"],"issn":["1868-8969"]},"status":"public","title":"Improved guarantees for vertex sparsification in planar graphs","intvolume":" 87","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11831","oa_version":"Published Version","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs.\r\n\r\nWe also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices."}],"publication":"25th Annual European Symposium on Algorithms","citation":{"chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” In 25th Annual European Symposium on Algorithms, Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPICS.ESA.2017.44.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 25th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” 25th Annual European Symposium on Algorithms, vol. 87, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPICS.ESA.2017.44.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” in 25th Annual European Symposium on Algorithms, Vienna, Austria, 2017, vol. 87.","apa":"Goranci, G., Henzinger, M. H., & Peng, P. (2017). Improved guarantees for vertex sparsification in planar graphs. In 25th Annual European Symposium on Algorithms (Vol. 87). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2017.44","ista":"Goranci G, Henzinger MH, Peng P. 2017. Improved guarantees for vertex sparsification in planar graphs. 25th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 87, 44.","ama":"Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. In: 25th Annual European Symposium on Algorithms. Vol 87. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPICS.ESA.2017.44"},"date_published":"2017-09-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No"},{"month":"11","publication_identifier":{"issn":["1432-4350"],"eissn":["1433-0490"]},"language":[{"iso":"eng"}],"doi":"10.1007/s00224-017-9759-8","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://doi.org/10.1007/s00224-017-9759-8","open_access":"1"}],"extern":"1","date_created":"2022-08-17T11:14:12Z","date_updated":"2023-02-21T16:29:58Z","volume":61,"author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"full_name":"Dvořák, Wolfgang","first_name":"Wolfgang","last_name":"Dvořák"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"last_name":"Starnberger","first_name":"Martin","full_name":"Starnberger, Martin"}],"related_material":{"record":[{"id":"11837","status":"public","relation":"earlier_version"}]},"publication_status":"published","publisher":"Springer Nature","year":"2017","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2017-11-01T00:00:00Z","article_type":"original","page":"948-986","publication":"Theory of Computing Systems","citation":{"ieee":"S. Bhattacharya, W. Dvořák, M. H. Henzinger, and M. Starnberger, “Welfare maximization with friends-of-friends network externalities,” Theory of Computing Systems, vol. 61, no. 4. Springer Nature, pp. 948–986, 2017.","apa":"Bhattacharya, S., Dvořák, W., Henzinger, M. H., & Starnberger, M. (2017). Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. Springer Nature. https://doi.org/10.1007/s00224-017-9759-8","ista":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. 2017. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 61(4), 948–986.","ama":"Bhattacharya S, Dvořák W, Henzinger MH, Starnberger M. Welfare maximization with friends-of-friends network externalities. Theory of Computing Systems. 2017;61(4):948-986. doi:10.1007/s00224-017-9759-8","chicago":"Bhattacharya, Sayan, Wolfgang Dvořák, Monika H Henzinger, and Martin Starnberger. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems. Springer Nature, 2017. https://doi.org/10.1007/s00224-017-9759-8.","short":"S. Bhattacharya, W. Dvořák, M.H. Henzinger, M. Starnberger, Theory of Computing Systems 61 (2017) 948–986.","mla":"Bhattacharya, Sayan, et al. “Welfare Maximization with Friends-of-Friends Network Externalities.” Theory of Computing Systems, vol. 61, no. 4, Springer Nature, 2017, pp. 948–86, doi:10.1007/s00224-017-9759-8."},"abstract":[{"lang":"eng","text":"Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1−1/e). (2) On the positive side we present (i) an 𝑂(𝑛√)-approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a 518(1−1/𝑒)-approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a 12(1−1/𝑒)-approximation algorithm."}],"issue":"4","type":"journal_article","oa_version":"Published Version","status":"public","title":"Welfare maximization with friends-of-friends network externalities","intvolume":" 61","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11903"}]