Cover Image

A Lossless Deamortization for Dynamic Greedy Set Cover

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Solomon, Shay, Uzrad, Amitai, Zhang, Tianyi
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Engineering Algorithms for Dynamic Greedy Set Cover
by: Uzrad, Amitai
Published: (2026)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
by: Bukov, Anton, et al.
Published: (2023)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
by: La, An, et al.
Published: (2025)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Greedy Dynamic Matching
by: Arnosti, Nick, et al.
Published: (2025)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

From Dynamic Programs to Greedy Algorithms
by: van Melkebeek, Dieter
Published: (2025)

Dynamic Pricing Algorithms for Online Set Cover
by: Bender, Max, et al.
Published: (2024)

Potential-Based Greedy Matching for Dynamic Delivery Pooling
by: Ma, Hongyao, et al.
Published: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Fair Set Cover
by: Dehghankar, Mohsen, et al.
Published: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
by: Bhattacharya, Sayan, et al.
Published: (2025)

Maximal Covering Location Problem: A Set Coverage Approach Using Dynamic Programming
by: Samanta, Sukanya, et al.
Published: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
by: Ma, Qingwen, et al.
Published: (2026)

New Greedy Spanners and Applications
by: Popova, Elizaveta, et al.
Published: (2026)

Greedy BST on Permutation Initial Tree
by: Pareek, Akash
Published: (2024)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
by: Bhangale, Amey, et al.
Published: (2026)

Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
by: Nguyen, Hue T., et al.
Published: (2025)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
by: Chen, Wenjing, et al.
Published: (2023)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

QuaRs: A Transform for Better Lossless Compression of Integers
by: Matt, Jonas G.
Published: (2025)

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
by: Le, Hung, et al.
Published: (2021)

Greedy Completion for Weighted $(α,β)$-Spanners
by: Tzalik, Elad
Published: (2026)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
by: Cáceres, Manuel, et al.
Published: (2025)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
by: Derakhshan, Mahsa, et al.
Published: (2026)

Online Disjoint Set Covers: Randomization is not Necessary
by: Bienkowski, Marcin, et al.
Published: (2024)