42 Search Results for "Henzinger, Monika"


Document
Electrical Flows for Polylogarithmic Competitive Oblivious Routing

Authors: Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. In this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth.

Cite as

Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. Electrical Flows for Polylogarithmic Competitive Oblivious Routing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{goranci_et_al:LIPIcs.ITCS.2024.55,
  author =	{Goranci, Gramoz and Henzinger, Monika and R\"{a}cke, Harald and Sachdeva, Sushant and Sricharan, A. R.},
  title =	{{Electrical Flows for Polylogarithmic Competitive Oblivious Routing}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{55:1--55:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.55},
  URN =		{urn:nbn:de:0030-drops-195830},
  doi =		{10.4230/LIPIcs.ITCS.2024.55},
  annote =	{Keywords: oblivious routing, electrical flows}
}
Document
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems

Authors: Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.

Cite as

Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 62:1-62:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2024.62,
  author =	{Henzinger, Monika and Saha, Barna and Seybold, Martin P. and Ye, Christopher},
  title =	{{On the Complexity of Algorithms with Predictions for Dynamic Graph Problems}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{62:1--62:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.62},
  URN =		{urn:nbn:de:0030-drops-195907},
  doi =		{10.4230/LIPIcs.ITCS.2024.62},
  annote =	{Keywords: Dynamic Graph Algorithms, Algorithms with Predictions}
}
Document
Track A: Algorithms, Complexity and Games
Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Authors: Gramoz Goranci and Monika Henzinger

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We show an (1+ε)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m^{1/2+o(1)} ε^{-1/2} amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in Õ(n^{5/2}) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.

Cite as

Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{goranci_et_al:LIPIcs.ICALP.2023.69,
  author =	{Goranci, Gramoz and Henzinger, Monika},
  title =	{{Efficient Data Structures for Incremental Exact and Approximate Maximum Flow}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.69},
  URN =		{urn:nbn:de:0030-drops-181212},
  doi =		{10.4230/LIPIcs.ICALP.2023.69},
  annote =	{Keywords: dynamic graph algorithms, maximum flow, data structures}
}
Document
Track A: Algorithms, Complexity and Games
Faster Submodular Maximization for Several Classes of Matroids

Authors: Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014]. To achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.

Cite as

Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng. Faster Submodular Maximization for Several Classes of Matroids. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ICALP.2023.74,
  author =	{Henzinger, Monika and Liu, Paul and Vondr\'{a}k, Jan and Zheng, Da Wei},
  title =	{{Faster Submodular Maximization for Several Classes of Matroids}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.74},
  URN =		{urn:nbn:de:0030-drops-181267},
  doi =		{10.4230/LIPIcs.ICALP.2023.74},
  annote =	{Keywords: submodular optimization, dynamic data structures, matching algorithms}
}
Document
Dynamic Maintenance of Monotone Dynamic Programs and Applications

Authors: Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1+ε)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0,W] using only polylog(n,W) bits, and to perform operations, such as (min,+)-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.

Cite as

Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. Dynamic Maintenance of Monotone Dynamic Programs and Applications. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.STACS.2023.36,
  author =	{Henzinger, Monika and Neumann, Stefan and R\"{a}cke, Harald and Schmid, Stefan},
  title =	{{Dynamic Maintenance of Monotone Dynamic Programs and Applications}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.36},
  URN =		{urn:nbn:de:0030-drops-176889},
  doi =		{10.4230/LIPIcs.STACS.2023.36},
  annote =	{Keywords: Dynamic programming, dynamic algorithms, data structures}
}
Document
Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks

Authors: Antoine El-Hayek, Monika Henzinger, and Stefan Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n. We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem. Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem. For the two latter problems no upper or lower bounds were previously known.

Cite as

Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 47:1-47:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{elhayek_et_al:LIPIcs.ITCS.2023.47,
  author =	{El-Hayek, Antoine and Henzinger, Monika and Schmid, Stefan},
  title =	{{Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{47:1--47:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.47},
  URN =		{urn:nbn:de:0030-drops-175502},
  doi =		{10.4230/LIPIcs.ITCS.2023.47},
  annote =	{Keywords: broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity}
}
Document
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems

Authors: Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)


Abstract
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.

Cite as

Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2023.69,
  author =	{Henzinger, Monika and Jin, Billy and Peng, Richard and Williamson, David P.},
  title =	{{A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{69:1--69:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.69},
  URN =		{urn:nbn:de:0030-drops-175720},
  doi =		{10.4230/LIPIcs.ITCS.2023.69},
  annote =	{Keywords: Laplacian solver, electrical flow, data structure}
}
Document
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs

Authors: Monika Henzinger, Ami Paz, and A. R. Sricharan

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions. Prior work has shown strong conditional lower bounds for general dynamic graphs, yet graph families that arise in practice often exhibit structural properties that the existing lower bound constructions do not possess. We study three specific graph families that are ubiquitous, namely constant-degree graphs, power-law graphs, and expander graphs, and give the first conditional lower bounds for them. Our results show that even when restricting our attention to one of these graph classes, any algorithm for fundamental graph problems such as distance computation or approximation or maximum matching, cannot simultaneously achieve a sub-polynomial update time and query time. For example, we show that the same lower bounds as for general graphs hold for maximum matching and (s,t)-distance in constant-degree graphs, power-law graphs or expanders. Namely, in an m-edge graph, there exists no dynamic algorithms with both O(m^{1/2 - ε}) update time and O(m^{1 -ε}) query time, for any small ε > 0. Note that for (s,t)-distance the trivial dynamic algorithm achieves an almost matching upper bound of constant update time and O(m) query time. We prove similar bounds for the other graph families and for other fundamental problems such as densest subgraph detection and perfect matching.

Cite as

Monika Henzinger, Ami Paz, and A. R. Sricharan. Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 65:1-65:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2022.65,
  author =	{Henzinger, Monika and Paz, Ami and Sricharan, A. R.},
  title =	{{Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{65:1--65:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.65},
  URN =		{urn:nbn:de:0030-drops-170035},
  doi =		{10.4230/LIPIcs.ESA.2022.65},
  annote =	{Keywords: Dynamic graph algorithms, Expander graphs, Power-law graphs}
}
Document
Invited Talk
Modern Dynamic Data Structures (Invited Talk)

Authors: Monika Henzinger

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
We give an overview of differentially private dynamic data structure, aka differentially private algorithms under continual release.

Cite as

Monika Henzinger. Modern Dynamic Data Structures (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{henzinger:LIPIcs.MFCS.2022.2,
  author =	{Henzinger, Monika},
  title =	{{Modern Dynamic Data Structures}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.2},
  URN =		{urn:nbn:de:0030-drops-168009},
  doi =		{10.4230/LIPIcs.MFCS.2022.2},
  annote =	{Keywords: Differential privacy, data structures}
}
Document
Leximax Approximations and Representative Cohort Selection

Authors: Monika Henzinger, Charlotte Peale, Omer Reingold, and Judy Hanwen Shen

Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)


Abstract
Finding a representative cohort from a broad pool of candidates is a goal that arises in many contexts such as choosing governing committees and consumer panels. While there are many ways to define the degree to which a cohort represents a population, a very appealing solution concept is lexicographic maximality (leximax) which offers a natural (pareto-optimal like) interpretation that the utility of no population can be increased without decreasing the utility of a population that is already worse off. However, finding a leximax solution can be highly dependent on small variations in the utility of certain groups. In this work, we explore new notions of approximate leximax solutions with three distinct motivations: better algorithmic efficiency, exploiting significant utility improvements, and robustness to noise. Among other definitional contributions, we give a new notion of an approximate leximax that satisfies a similarly appealing semantic interpretation and relate it to algorithmically-feasible approximate leximax notions. When group utilities are linear over cohort candidates, we give an efficient polynomial-time algorithm for finding a leximax distribution over cohort candidates in the exact as well as in the approximate setting. Furthermore, we show that finding an integer solution to leximax cohort selection with linear utilities is NP-Hard.

Cite as

Monika Henzinger, Charlotte Peale, Omer Reingold, and Judy Hanwen Shen. Leximax Approximations and Representative Cohort Selection. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.FORC.2022.2,
  author =	{Henzinger, Monika and Peale, Charlotte and Reingold, Omer and Shen, Judy Hanwen},
  title =	{{Leximax Approximations and Representative Cohort Selection}},
  booktitle =	{3rd Symposium on Foundations of Responsible Computing (FORC 2022)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-226-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{218},
  editor =	{Celis, L. Elisa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.2},
  URN =		{urn:nbn:de:0030-drops-165258},
  doi =		{10.4230/LIPIcs.FORC.2022.2},
  annote =	{Keywords: fairness, cohort selection, leximin, maxmin}
}
Document
Track A: Algorithms, Complexity and Games
Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring

Authors: Aleksander B. G. Christiansen and Eva Rotenberg

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
The arboricity α of a graph is the smallest number of forests necessary to cover its edges, and an arboricity decomposition of a graph is a decomposition of its edges into forests. The best near-linear time algorithm for arboricity decomposition guarantees at most α +2 forests if the graph has arboricity α (Blumenstock and Fischer [Markus Blumenstock and Frank Fischer, 2020]). In this paper, we study arboricity decomposition for dynamic graphs, that is, graphs that are subject to insertions and deletions of edges. We give an algorithm that, provided the arboricity of the dynamic graph never exceeds α, maintains an α+2 arboricity decomposition of the graph in poly(log n,α) update time, thus matching the number of forests currently obtainable in near-linear time for static (non-changing) graphs. Our construction goes via dynamic bounded out-degree orientations, and we present a fully-dynamic algorithm that explicitly orients the edges of the dynamic graph, such that no vertex has an out-degree exceeding ⌊ (1+ε)α ⌋ + 2. Our algorithm is deterministic and has a worst-case update time of O(ε^{-6}α² log³ n). The state-of-the-art explicit, deterministic, worst-case algorithm for bounded out-degree orientations maintains a β⋅ α + log_β n out-orientation in O(β²α²+βαlog_β n) time [Tsvi Kopelowitz et al., 2014]. As a consequence, we get an algorithm that maintains an implicit vertex colouring with 4⋅ 2^α colours, in amortised poly-log n update time, and with O(α log n) worst-case query time. Thus, at the expense of log n-factors in the update time, we improve on the number of colours from 2^O(α) to O(2^α) compared to the state-of-the-art for implicit dynamic colouring [Monika Henzinger et al., 2020].

Cite as

Aleksander B. G. Christiansen and Eva Rotenberg. Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{christiansen_et_al:LIPIcs.ICALP.2022.42,
  author =	{Christiansen, Aleksander B. G. and Rotenberg, Eva},
  title =	{{Fully-Dynamic \alpha + 2 Arboricity Decompositions and Implicit Colouring}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.42},
  URN =		{urn:nbn:de:0030-drops-163835},
  doi =		{10.4230/LIPIcs.ICALP.2022.42},
  annote =	{Keywords: Dynamic graphs, bounded arboricity, graph colouring, data structures}
}
Document
Track A: Algorithms, Complexity and Games
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Authors: Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [Sherman, 2017], optimal transport [Arun Jambulapati et al., 2019], and bipartite matching [Sepehr Assadi et al., 2022]. We develop efficient near-linear time, high-accuracy solvers for regularized variants of these games. Beyond the immediate applications of such solvers for computing Sinkhorn distances, a prominent tool in machine learning, we show that these solvers can be used to obtain improved running times for maintaining a (fractional) ε-approximate maximum matching in a dynamic decremental bipartite graph against an adaptive adversary. We give a generic framework which reduces this dynamic matching problem to solving regularized graph-structured optimization problems to high accuracy. Through our reduction framework, our regularized box-simplex game solver implies a new algorithm for dynamic decremental bipartite matching in total time Õ(m ⋅ ε^{-3}), from an initial graph with m edges and n nodes. We further show how to use recent advances in flow optimization [Chen et al., 2022] to improve our runtime to m^{1 + o(1)} ⋅ ε^{-2}, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of Õ(m ⋅ ε^{-4}) [Aaron Bernstein et al., 2020] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms.

Cite as

Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 77:1-77:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{jambulapati_et_al:LIPIcs.ICALP.2022.77,
  author =	{Jambulapati, Arun and Jin, Yujia and Sidford, Aaron and Tian, Kevin},
  title =	{{Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{77:1--77:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.77},
  URN =		{urn:nbn:de:0030-drops-164181},
  doi =		{10.4230/LIPIcs.ICALP.2022.77},
  annote =	{Keywords: bipartite matching, decremental matching, dynamic algorithms, continuous optimization, box-simplex games, primal-dual method}
}
Document
Fully Dynamic Four-Vertex Subgraph Counting

Authors: Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.

Cite as

Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SAND.2022.18,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Hua, Qi Cheng},
  title =	{{Fully Dynamic Four-Vertex Subgraph Counting}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.18},
  URN =		{urn:nbn:de:0030-drops-159608},
  doi =		{10.4230/LIPIcs.SAND.2022.18},
  annote =	{Keywords: Dynamic Graph Algorithms, Subgraph Counting, Motif Search}
}
Document
Invited Talk
Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk)

Authors: Kathrin Hanauer, Monika Henzinger, and Christian Schulz

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.

Cite as

Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 1:1-1:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SAND.2022.1,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Schulz, Christian},
  title =	{{Recent Advances in Fully Dynamic Graph Algorithms}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{1:1--1:47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.1},
  URN =		{urn:nbn:de:0030-drops-159434},
  doi =		{10.4230/LIPIcs.SAND.2022.1},
  annote =	{Keywords: fully dynamic graph algorithms, survey}
}
Document
Differentially Private Algorithms for Graphs Under Continual Observation

Authors: Hendrik Fichtenberger, Monika Henzinger, and Lara Ost

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T. We also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range.

Cite as

Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fichtenberger_et_al:LIPIcs.ESA.2021.42,
  author =	{Fichtenberger, Hendrik and Henzinger, Monika and Ost, Lara},
  title =	{{Differentially Private Algorithms for Graphs Under Continual Observation}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.42},
  URN =		{urn:nbn:de:0030-drops-146230},
  doi =		{10.4230/LIPIcs.ESA.2021.42},
  annote =	{Keywords: differential privacy, continual observation, dynamic graph algorithms}
}
  • Refine by Author
  • 39 Henzinger, Monika
  • 8 Goranci, Gramoz
  • 5 Chatterjee, Krishnendu
  • 5 Schulz, Christian
  • 4 Neumann, Stefan
  • Show More...

  • Refine by Classification
  • 13 Theory of computation → Dynamic graph algorithms
  • 4 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Facility location and clustering
  • 1 General and reference → Surveys and overviews
  • 1 Information systems → Clustering
  • Show More...

  • Refine by Keyword
  • 5 data structures
  • 4 Dynamic Graph Algorithms
  • 4 Dynamic graph algorithms
  • 4 graph games
  • 3 conditional lower bounds
  • Show More...

  • Refine by Type
  • 42 document

  • Refine by Publication Year
  • 7 2017
  • 7 2022
  • 6 2020
  • 5 2023
  • 4 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail