Cover Image

Online Rounding for Set Cover under Subset Arrivals

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Byrka, Jarosław, Shin, Yongho
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Chromatic correlation clustering via cluster LP
by: Abbasi, Fateme, et al.
Published: (2025)

Servicing Matched Client Pairs with Facilities
by: Abbasi, Fateme, et al.
Published: (2026)

$k$-Clustering via Iterative Randomized Rounding
by: Byrka, Jarosław, et al.
Published: (2026)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

On the Bidirected Cut Relaxation for Steiner Forest
by: Byrka, Jarosław, et al.
Published: (2024)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
by: Byrka, Jarosław, et al.
Published: (2024)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Adaptive Multi-Round Allocation with Stochastic Arrivals
by: Pan, Yuqi, et al.
Published: (2026)

Learning-Augmented Online Bipartite Fractional Matching
by: Choo, Davin, et al.
Published: (2025)

Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
by: Byrka, Jarosław, et al.
Published: (2025)

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

Online Multi-level Aggregation with Delays and Stochastic Arrivals
by: Mari, Mathieu, et al.
Published: (2024)

Online Rounding Schemes for $ k $-Rental Problems
by: Nekouyan, Hossein, et al.
Published: (2025)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
by: Sun, Enze, et al.
Published: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
by: Bai, Tian
Published: (2025)

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
by: Ma, Will
Published: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

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

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
by: Bai, Tian, et al.
Published: (2022)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
by: Lee, Changyeol, et al.
Published: (2025)

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

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Dynamic Batching of Online Arrivals to Leverage Economies of Scale
by: Bhimaraju, Akhil, et al.
Published: (2023)

Online Coalition Formation under Random Arrival or Coalition Dissolution
by: Bullinger, Martin, et al.
Published: (2023)

A Nonparametric Framework for Online Stochastic Matching with Correlated Arrivals
by: Aouad, Ali, et al.
Published: (2022)

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

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

Learning Dependency Models for Subset Repair
by: Li, Haoda, et al.
Published: (2025)

Approximate Min-Sum Subset Convolution
by: Stoian, Mihail
Published: (2024)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
by: Chan, Timothy M.
Published: (2026)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

Learning-Augmented Online Covering Problems
by: Ameli, Afrouz Jabal, et al.
Published: (2025)

Online Bin Covering with Frequency Predictions
by: Berg, Magnus, et al.
Published: (2024)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)

Estimating Correlation Clustering Cost in Node-Arrival Stream
by: Liu, Kaiwen, et al.
Published: (2026)

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