Monika Henzinger
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Monika Henzinger has a total of 87 co-authors. Here are the top co-authors by number of shared publications:
- Christian Schulz
Heidelberg University
8 shared publications - Krishnendu Chatterjee
IST Austria, Klosterneuburg, Austria
6 shared publications - Gramoz Goranci
Faculty of Computer Science, University of Vienna, Vienna, Austria
5 shared publications - Danupon Nanongkai
MPI-INF Germany
4 shared publications - Sebastian Forster
University of Salzburg, Salzburg, Austria
4 shared publications - Stefan Neumann
TU Wien, Vienna, Austria
4 shared publications
Latest Publications
- Open Access
- 14 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 347-361
Edit-Neighboring Data Streams and Privacy under Continual Observation
- 14 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 347-361
Open AccessEdit-Neighboring Data Streams and Privacy under Continual Observation
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-24
Incremental Approximate Maximum Flow via Residual Graph Sparsification
We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs.- 6 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-24
Open AccessIncremental Approximate Maximum Flow via Residual Graph Sparsification
We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs. - Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1417-1428
An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks. There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log9n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators. Crucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1417-1428
Open AccessAn Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks. There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log9n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators. Crucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights.
- Open Access
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-26
Concurrent Composition for Differentially Private Continual Mechanisms
Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously over a long period of time, making more statistical releases as either queries come in or the dataset is updated. In this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that support dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion of neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition theorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries and dataset updates to the different composed mechanisms. Previous concurrent composition theorems for differential privacy were only for the case when the dataset is static, with no adaptive updates. We also give the first interactive and continual generalizations of the ''parallel composition theorem'' for noninteractive differential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem holds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure differential privacy, but it fails to hold for composing approximately differentially private mechanisms with dataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent filter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We extend these results to other measures of differential privacy, including Rényi DP and ƒ-DP. We then formalize a set of general conditions on a continual mechanism M that runs multiple continual sub-mechanisms such that the privacy guarantees of M follow directly using the above concurrent composition theorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular privacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the case of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries. We also provide a framework that simplifies the analysis of local differential privacy when the protocol includes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core decomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu.
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-26
Open AccessConcurrent Composition for Differentially Private Continual Mechanisms
Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously over a long period of time, making more statistical releases as either queries come in or the dataset is updated. In this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that support dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion of neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition theorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries and dataset updates to the different composed mechanisms. Previous concurrent composition theorems for differential privacy were only for the case when the dataset is static, with no adaptive updates. We also give the first interactive and continual generalizations of the ''parallel composition theorem'' for noninteractive differential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem holds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure differential privacy, but it fails to hold for composing approximately differentially private mechanisms with dataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent filter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We extend these results to other measures of differential privacy, including Rényi DP and ƒ-DP. We then formalize a set of general conditions on a continual mechanism M that runs multiple continual sub-mechanisms such that the privacy guarantees of M follow directly using the above concurrent composition theorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular privacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the case of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries. We also provide a framework that simplifies the analysis of local differential privacy when the protocol includes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core decomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu.
- Open Access
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-27
Improved Lower Bounds for Privacy under Continual Release
We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on the additive error for insertions-only graph problems such as maximum matching, degree histogram and k -core number computation. These results represent an exponential improvement on the polylogarithmic lower bounds of Fichtenberger, Henzinger and Ost [ESA 2021] for the former two problems, and are the first lower bounds in the continual release setting for the latter problem. Our results run counter to the intuition that the difference between insertions-only vs fully dynamic updates causes the gap between polylogarithmic and polynomial additive error. Indeed, we show that for estimating the size of the maximum matching or k -core number of a vertex, allowing small multiplicative approximations is what brings the additive error down to polylogarithmic. We complement these results with improved upper bounds on the additive error when no multiplicative approximation is allowed. Beyond graphs, our techniques also show that polynomial additive error is unavoidable for the Simultaneous Norm Estimation problem in the insertions-only setting. When multiplicative approximations are allowed, we circumvent this lower bound by giving the first continual mechanism with polylogarithmic additive error under (1 + ζ) multiplicative approximations, for any ζ > 0, for estimating all monotone symmetric norms simultaneously. In the item-level setting, we show polynomial lower bounds on the product of the multiplicative and the additive error of continual mechanisms for a large range of graph problems. To the best of our knowledge, these are the first lower bounds shown for any differentially private mechanism under continual release with multiplicative error. To obtain these results, we prove a new lower bound on the product of multiplicative and additive error for the 1-W ay -M arginals problem, and give reductions from 1-W ay -M arginals to our desired graph problems. This generalizes the prior results of Hardt and Talwar [STOC 2010] and Bun, Ullman and Vadhan [STOC 2014, SIAM J. Comput. 2018], who gave lower bounds on the additive error for the special case of mechanisms with no multiplicative error.
- 12 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (2) , 1-27
Open AccessImproved Lower Bounds for Privacy under Continual Release
We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on the additive error for insertions-only graph problems such as maximum matching, degree histogram and k -core number computation. These results represent an exponential improvement on the polylogarithmic lower bounds of Fichtenberger, Henzinger and Ost [ESA 2021] for the former two problems, and are the first lower bounds in the continual release setting for the latter problem. Our results run counter to the intuition that the difference between insertions-only vs fully dynamic updates causes the gap between polylogarithmic and polynomial additive error. Indeed, we show that for estimating the size of the maximum matching or k -core number of a vertex, allowing small multiplicative approximations is what brings the additive error down to polylogarithmic. We complement these results with improved upper bounds on the additive error when no multiplicative approximation is allowed. Beyond graphs, our techniques also show that polynomial additive error is unavoidable for the Simultaneous Norm Estimation problem in the insertions-only setting. When multiplicative approximations are allowed, we circumvent this lower bound by giving the first continual mechanism with polylogarithmic additive error under (1 + ζ) multiplicative approximations, for any ζ > 0, for estimating all monotone symmetric norms simultaneously. In the item-level setting, we show polynomial lower bounds on the product of the multiplicative and the additive error of continual mechanisms for a large range of graph problems. To the best of our knowledge, these are the first lower bounds shown for any differentially private mechanism under continual release with multiplicative error. To obtain these results, we prove a new lower bound on the product of multiplicative and additive error for the 1-W ay -M arginals problem, and give reductions from 1-W ay -M arginals to our desired graph problems. This generalizes the prior results of Hardt and Talwar [STOC 2010] and Bun, Ullman and Vadhan [STOC 2014, SIAM J. Comput. 2018], who gave lower bounds on the additive error for the special case of mechanisms with no multiplicative error.
- Open Access
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 1016-1027
Expander Hierarchies for Normalized Cuts on Graphs
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 1016-1027
Open AccessExpander Hierarchies for Normalized Cuts on Graphs
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.
- Open Access
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple $n$-vertex, $m$-edge graph $G$ undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G$ in $\tilde{O}(n)$ worst-case update time and $\tilde{O}(m^{1-1/31})$ amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms either assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results provide an affirmative answer to an open question posed by Thorup [Combinatorica'07].Open AccessFully Dynamic Exact Edge Connectivity in Sublinear Time
Given a simple $n$-vertex, $m$-edge graph $G$ undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G$ in $\tilde{O}(n)$ worst-case update time and $\tilde{O}(m^{1-1/31})$ amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms either assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results provide an affirmative answer to an open question posed by Thorup [Combinatorica'07]. - Open Access
Almost Tight Error Bounds on Differentially Private Continual Counting
The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In this case, a concrete bound on the error is very relevant to reduce the privacy parameter. The standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is both asymptotically optimal and a factor 10 smaller than the error of the binary mechanism. We also show that the constants in our analysis are almost tight by giving non-asymptotic lower and upper bounds that differ only in the constants of lower-order terms. Our algorithm is a matrix mechanism for the counting matrix and takes constant time per release. We also use our explicit factorization of the counting matrix to give an upper bound on the excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022). Our lower bound for any continual counting mechanism is the first tight lower bound on continual counting under approximate differential privacy. It is achieved using a new lower bound on a certain factorization norm, denoted by $\gamma_F(\cdot)$, in terms of the singular values of the matrix. In particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times n}$, \[ \gamma_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$ denotes the Schatten-1 norm. We believe this technique will be useful in proving lower bounds for a larger class of linear queries. To illustrate the power of this technique, we show the first lower bound on the mean squared error for answering parity queries.Open AccessAlmost Tight Error Bounds on Differentially Private Continual Counting
The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In this case, a concrete bound on the error is very relevant to reduce the privacy parameter. The standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is both asymptotically optimal and a factor 10 smaller than the error of the binary mechanism. We also show that the constants in our analysis are almost tight by giving non-asymptotic lower and upper bounds that differ only in the constants of lower-order terms. Our algorithm is a matrix mechanism for the counting matrix and takes constant time per release. We also use our explicit factorization of the counting matrix to give an upper bound on the excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022). Our lower bound for any continual counting mechanism is the first tight lower bound on continual counting under approximate differential privacy. It is achieved using a new lower bound on a certain factorization norm, denoted by $\gamma_F(\cdot)$, in terms of the singular values of the matrix. In particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times n}$, \[ \gamma_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$ denotes the Schatten-1 norm. We believe this technique will be useful in proving lower bounds for a larger class of linear queries. To illustrate the power of this technique, we show the first lower bound on the mean squared error for answering parity queries. - Open Access
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-triangular matrices can be used in the continual observation model. More specifically, we give an explicit factorization for the counting matrix $M_\mathsf{count}$ and upper bound the error explicitly. We also give a fine-grained analysis, specifying the exact constant in the upper bound. Our analysis is based on upper and lower bounds of the {\em completely bounded norm} (cb-norm) of $M_\mathsf{count}$. Along the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal on Matrix Analysis and Applications, 1993) on the cb-norm of $M_\mathsf{count}$ for a large range of the dimension of $M_\mathsf{count}$. Furthermore, we are the first to give concrete error bounds for various problems under continual observation such as binary counting, maintaining a histogram, releasing an approximately cut-preserving synthetic graph, many graph-based statistics, and substring and episode counting. Finally, we note that our result can be used to get a fine-grained error bound for non-interactive local learning {and the first lower bounds on the additive error for $(\epsilon,\delta)$-differentially-private counting under continual observation.} Subsequent to this work, Henzinger et al. (SODA2023) showed that our factorization also achieves fine-grained mean-squared error.Open AccessConstant matters: Fine-grained Complexity of Differentially Private Continual Observation
We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-triangular matrices can be used in the continual observation model. More specifically, we give an explicit factorization for the counting matrix $M_\mathsf{count}$ and upper bound the error explicitly. We also give a fine-grained analysis, specifying the exact constant in the upper bound. Our analysis is based on upper and lower bounds of the {\em completely bounded norm} (cb-norm) of $M_\mathsf{count}$. Along the way, we improve the best-known bound of 28 years by Mathias (SIAM Journal on Matrix Analysis and Applications, 1993) on the cb-norm of $M_\mathsf{count}$ for a large range of the dimension of $M_\mathsf{count}$. Furthermore, we are the first to give concrete error bounds for various problems under continual observation such as binary counting, maintaining a histogram, releasing an approximately cut-preserving synthetic graph, many graph-based statistics, and substring and episode counting. Finally, we note that our result can be used to get a fine-grained error bound for non-interactive local learning {and the first lower bounds on the additive error for $(\epsilon,\delta)$-differentially-private counting under continual observation.} Subsequent to this work, Henzinger et al. (SODA2023) showed that our factorization also achieves fine-grained mean-squared error. - 6 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (5) , 1132-1192
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal [Formula: see text] approximation factor. (Throughout, [Formula: see text], [Formula: see text], [Formula: see text], and [Formula: see text] are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when [Formula: see text], this was achieved by a deterministic [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time by Gupta et al. [ Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this paper we consider the low-frequency range, when [Formula: see text], and obtain deterministic algorithms with a [Formula: see text]-approximation ratio and the following guarantees on the update time. (1) [Formula: see text] amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was [Formula: see text] of Bhattacharya, Henzinger, and Italiano [ Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only result with [Formula: see text]-approximation was that of Abboud et al. [ Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125], who designed a randomized [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time. (2) [Formula: see text] amortized update time: This result improves the above update time bound for most values of [Formula: see text] in the low-frequency range, i.e., [Formula: see text]. It is also the first result that is independent of [Formula: see text] and [Formula: see text]. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [ Deterministically maintaining a [Formula: see text]-approximate minimum vertex cover in [Formula: see text] amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex cover (i.e., when [Formula: see text] and [Formula: see text]). (3) [Formula: see text] worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the [Formula: see text] worst-case update time for the unweighted dynamic vertex cover problem (i.e., when [Formula: see text] and [Formula: see text]) of Bhattacharya, Henzinger, and Nanongkai [ Fully dynamic approximate maximum matching and minimum vertex cover in [Formula: see text] worst case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds.
- 6 October 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 52 (5) , 1132-1192
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal [Formula: see text] approximation factor. (Throughout, [Formula: see text], [Formula: see text], [Formula: see text], and [Formula: see text] are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when [Formula: see text], this was achieved by a deterministic [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time by Gupta et al. [ Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this paper we consider the low-frequency range, when [Formula: see text], and obtain deterministic algorithms with a [Formula: see text]-approximation ratio and the following guarantees on the update time. (1) [Formula: see text] amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was [Formula: see text] of Bhattacharya, Henzinger, and Italiano [ Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only result with [Formula: see text]-approximation was that of Abboud et al. [ Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125], who designed a randomized [Formula: see text]-approximation algorithm with [Formula: see text] amortized update time. (2) [Formula: see text] amortized update time: This result improves the above update time bound for most values of [Formula: see text] in the low-frequency range, i.e., [Formula: see text]. It is also the first result that is independent of [Formula: see text] and [Formula: see text]. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [ Deterministically maintaining a [Formula: see text]-approximate minimum vertex cover in [Formula: see text] amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex cover (i.e., when [Formula: see text] and [Formula: see text]). (3) [Formula: see text] worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the [Formula: see text] worst-case update time for the unweighted dynamic vertex cover problem (i.e., when [Formula: see text] and [Formula: see text]) of Bhattacharya, Henzinger, and Nanongkai [ Fully dynamic approximate maximum matching and minimum vertex cover in [Formula: see text] worst case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds.