Amitai Uzrad

collaborators

2 papers

cs.DS2024

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 $n$ elements and…

cs.DS2023

Dynamic $((1 + ε) ln n)$ -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 $ln n$ -approximation and a primal-dual $f$ -approximation, where $n$ is the universe size and $f$ is the…

A Lossless Deamortization for Dynamic Greedy Set Cover

Dynamic ((1+ε)lnn)-Approximation Algorithms for Minimum Set Cover and Dominating Set

Dynamic $((1 + ε) ln n)$ -Approximation Algorithms for Minimum Set Cover and Dominating Set