5 papers
Engineering Algorithms for Dynamic Greedy Set Cover
Amitai Uzrad
In the dynamic set cover problem, the input is a dynamic universe of elements and a fixed collection of sets. As elements are inserted or deleted, the goal is to efficiently mainta…
Dynamic Set Cover with Worst-Case Recourse
Shay Solomon, Amitai Uzrad
In the dynamic set cover (SC) problem, the input is a dynamic universe of at most elements and a fixed collection of sets, where each element belongs to at most sets an…
A Lossless Deamortization for Dynamic Greedy Set Cover
Shay Solomon, Amitai Uzrad, Tianyi Zhang
The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most elements and…
Dynamic -Approximation Algorithms for Minimum Set Cover and Dominating Set
Shay Solomon, Amitai Uzrad
The minimum set cover (MSC) problem admits two classic algorithms: a greedy -approximation and a primal-dual -approximation, where is the universe size and is the…
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon +1
In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a -approximate maximum matching in fully dynamic {\em bipartite} graphs wi…