2026-07-22T04:53:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26030 2026-06-23T13:23:17Z ddc:004 open_access

Engineering Algorithms for Dynamic Greedy Set Cover Uzrad, Amitai Dynamic graphs set cover recourse 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 maintain an approximate minimum set cover. While the past decade has seen significant theoretical breakthroughs for this problem, a notable gap remains between theoretical design and practical performance, as no comprehensive experimental study currently exists to validate these results. In this paper, we bridge this gap by implementing and evaluating four greedy-based dynamic algorithms across a diverse range of real-world instances. We derive our implementations from state-of-the-art frameworks - such as [GKKP(STOC'17); SU(STOC'23); SUZ(FOCS'24)] - which we simplify by identifying and modifying intricate subroutines that optimize asymptotic bounds but hinder practical performance. We evaluate these algorithms based on solution quality (set cover size) and efficiency, which comprises update time - the time required to update the solution following each insertion/deletion - and recourse - the number of changes made to the solution per update. Each algorithm uses a parameter β to balance quality against efficiency; we investigate the influence of this tradeoff parameter on each algorithm and then perform a comparative analysis to evaluate the algorithms against each other. Our results provide the first practical insights into which algorithmic strategies provide the most value in realistic scenarios. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amitai Uzrad 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.26 urn:nbn:de:0030-drops-260308 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode