Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Solomon, Shay, Uzrad, Amitai
Format:	Preprint
Published:	2023
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)

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

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)

Exact Optimization for Minimum Dominating Sets
by: Zhu, Enqiang, et al.
Published: (2025)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

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

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

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

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

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

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

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

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

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

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

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
by: Adil, Deeksha, et al.
Published: (2024)

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

Dominating Set with Quotas: Balancing Coverage and Constraints
by: Chatterjee, Sobyasachi, et al.
Published: (2026)

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

Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
by: Kesselheim, Thomas, et al.
Published: (2025)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

Revisiting a Successful Reduction Rule for Dominating Set
by: Geis, Lukas, et al.
Published: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

Analysis of a Random Local Search Algorithm for Dominating Set
by: Higl, Hendrik
Published: (2026)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

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

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

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

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
by: Karathanasis, Konstantinos, et al.
Published: (2025)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)