Imagen de Portada

Online Disjoint Set Covers: Randomization is not Necessary

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bienkowski, Marcin, Byrka, Jarosław, Jeż, Łukasz
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
por: Basiak, Mateusz, et al.
Publicado: (2025)

A Subquadratic Bound for Online Bisection
por: Bienkowski, Marcin, et al.
Publicado: (2023)

Online Bisection with Ring Demands
por: Basiak, Mateusz, et al.
Publicado: (2026)

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

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
por: Bienkowski, Marcin, et al.
Publicado: (2026)

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

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

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

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

Online Disjoint Spanning Trees and Polymatroid Bases
por: Chandrasekaran, Karthekeyan, et al.
Publicado: (2025)

Learning Minimum Linear Arrangement of Cliques and Lines
por: Dallot, Julien, et al.
Publicado: (2024)

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

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

Random Order Set Cover is as Easy as Offline
por: Gupta, Anupam, et al.
Publicado: (2021)

Disjoint Tours and the Price of Diversity
por: de Berg, Mark, et al.
Publicado: (2025)

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

Revisiting Directed Disjoint Paths on tournaments (and relatives)
por: Gomes, Guilherme C. M., et al.
Publicado: (2025)

Contract Scheduling with Distributional and Multiple Advice
por: Angelopoulos, Spyros, et al.
Publicado: (2024)

Connected k-Median with Disjoint and Non-disjoint Clusters
por: Eube, Jan, et al.
Publicado: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
por: Pilipczuk, Michał, et al.
Publicado: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
por: Ferdous, S M, et al.
Publicado: (2023)

Fair Set Cover
por: Dehghankar, Mohsen, et al.
Publicado: (2024)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
por: Bentert, Matthias, et al.
Publicado: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
por: Chitnis, Rajesh, et al.
Publicado: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
por: Choudhary, Keerti, et al.
Publicado: (2025)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
por: Włodarczyk, Michał
Publicado: (2024)

The Online Submodular Cover Problem
por: Gupta, Anupam, et al.
Publicado: (2025)

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

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

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

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

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

Engineering Algorithms for Dynamic Greedy Set Cover
por: Uzrad, Amitai
Publicado: (2026)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
por: Bucić, Matija, et al.
Publicado: (2025)

Minor Containment and Disjoint Paths in almost-linear time
por: Korhonen, Tuukka, et al.
Publicado: (2024)

On the Two Paths Theorem and the Two Disjoint Paths Problem
por: Humeau, Samuel, et al.
Publicado: (2025)

Online Algorithms with Randomly Infused Advice
por: Emek, Yuval, et al.
Publicado: (2023)

Online Matching in Geometric Random Graphs
por: Sentenac, Flore, et al.
Publicado: (2023)

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