Cover Image

Random Order Set Cover is as Easy as Offline

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Kehne, Gregory, Levin, Roie
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pairwise-Independent Contention Resolution
by: Gupta, Anupam, et al.
Published: (2024)

The Online Submodular Cover Problem
by: Gupta, Anupam, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

A Learning Perspective on Random-Order Covering Problems
by: Gupta, Anupam, et al.
Published: (2025)

Competitively Consistent Clustering
by: Buchbinder, Niv, et al.
Published: (2025)

Chasing Positive Bodies
by: Bhattacharya, Sayan, et al.
Published: (2023)

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

Prophet and Secretary at the Same Time
by: Kehne, Gregory, et al.
Published: (2025)

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

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems
by: Bhore, Sujoy, et al.
Published: (2026)

Steiner Forest: A Simplified Better-Than-2 Approximation
by: Gupta, Anupam, et al.
Published: (2025)

Trading Prophets with Initial Capital
by: Azar, Yossi, et al.
Published: (2025)

Competitive Bundle Trading
by: Azar, Yossi, et al.
Published: (2025)

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

Random-Order Interval Selection
by: Borodin, Allan, et al.
Published: (2024)

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

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

Tree Coloring: Random Order and Predictions
by: Frei, Fabian, et al.
Published: (2024)

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

Min-Sum Set Cover on Parallel Machines
by: Szyfelbein, Michał
Published: (2026)

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

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

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

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

Enumeration kernels for Vertex Cover and Feedback Vertex Set
by: Bougeret, Marin, et al.
Published: (2025)

Online Rounding for Set Cover under Subset Arrivals
by: Byrka, Jarosław, et al.
Published: (2025)

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

Why is My Route Different Today? An Algorithm for Explaining Route Selection
by: Schild, Aaron, et al.
Published: (2025)

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

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

Improved Parallel Algorithms for EF1 Allocations
by: Gowda, Kishen N, et al.
Published: (2026)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
by: Hashemi, Diba, et al.
Published: (2024)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

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

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

Matroid-Based TSP Rounding for Half-Integral Solutions
by: Gupta, Anupam, et al.
Published: (2021)

Range-Based Set Reconciliation via Range-Summarizable Order-Statistics Stores
by: Amparore, Elvio G.
Published: (2026)