Copertina

Online Edge Coloring is (Nearly) as Easy as Offline

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Blikstad, Joakim, Svensson, Ola, Vintan, Radu, Wajc, David
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Deterministic Online Bipartite Edge Coloring
di: Blikstad, Joakim, et al.
Pubblicazione: (2024)

Online Edge Coloring: Sharp Thresholds
di: Blikstad, Joakim, et al.
Pubblicazione: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
di: Blikstad, Joakim, et al.
Pubblicazione: (2026)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
di: Blikstad, Joakim, et al.
Pubblicazione: (2025)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
di: Blikstad, Joakim, et al.
Pubblicazione: (2024)

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

Online Matching: A Brief Survey
di: Huang, Zhiyi, et al.
Pubblicazione: (2024)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
di: Braverman, Mark, et al.
Pubblicazione: (2024)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
di: Buchbinder, Niv, et al.
Pubblicazione: (2025)

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

Faster Vizing and Near-Vizing Edge Coloring Algorithms
di: Assadi, Sepehr
Pubblicazione: (2024)

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

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
di: Elkin, Michael, et al.
Pubblicazione: (2024)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2026)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
di: Dhawan, Abhishek
Pubblicazione: (2024)

Dynamic Edge Coloring of Forests
di: Kaplan, Haim, et al.
Pubblicazione: (2026)

Combinatorial Stationary Prophet Inequalities
di: Patel, Neel, et al.
Pubblicazione: (2023)

Dimension-Free Correlated Sampling for the Hypersimplex
di: Joseph, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
di: Curticapean, Radu, et al.
Pubblicazione: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

Online versus Offline Adversaries in Property Testing
di: Kelman, Esty, et al.
Pubblicazione: (2024)

Data-Driven Solution Portfolios
di: Drygala, Marina, et al.
Pubblicazione: (2024)

Improved Streaming Edge Coloring
di: Chechik, Shiri, et al.
Pubblicazione: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

Faster Edge Coloring by Partition Sieving
di: Akmal, Shyan, et al.
Pubblicazione: (2025)

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

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
di: Crane, Alex, et al.
Pubblicazione: (2023)

Streaming Edge Coloring with Subquadratic Palette Size
di: Chechik, Shiri, et al.
Pubblicazione: (2023)

On the Complexity of Distributed Edge Coloring and Orientation Problems
di: Brandt, Sebastian, et al.
Pubblicazione: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
di: Das, Debarati, et al.
Pubblicazione: (2026)

Retriever Portfolios: A Principled Approach to Adaptive RAG
di: Stouras, Miltiadis, et al.
Pubblicazione: (2026)

Online List Labeling with Near-Logarithmic Writes
di: Seybold, Martin P.
Pubblicazione: (2024)

Nearly Tight Bounds for the Online Sorting Problem
di: Azar, Yossi, et al.
Pubblicazione: (2025)

Nearly Optimal Bounds for Stochastic Online Sorting
di: Hu, Yang
Pubblicazione: (2025)

A Near-Optimal Kernel for a Coloring Problem
di: Haviv, Ishay, et al.
Pubblicazione: (2025)

Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
di: Mieno, Takuya, et al.
Pubblicazione: (2024)

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