Imagen de Portada

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Jiang, Tianle, Zhang, Yuhao
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 Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
por: Pashkovich, Kanstantsin, et al.
Publicado: (2026)

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

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

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

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

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

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

Structural Parameterizations for Induced and Acyclic Matching
por: Lampis, Michael, et al.
Publicado: (2025)

The Power of Greedy for Online Minimum Cost Matching on the Line
por: Balkanski, Eric, et al.
Publicado: (2022)

Simpler Optimal Sorting from a Directed Acyclic Graph
por: van der Hoog, Ivor, et al.
Publicado: (2024)

Finding a Shortest $M$-link Path in a Monge Directed Acyclic Graph
por: Wan, Joy Z.
Publicado: (2024)

Edge-weighted Matching in the Dark
por: Huang, Zhiyi, et al.
Publicado: (2025)

Online Makespan Minimization: Beat LPT by Dynamic Locking
por: Wang, Zhaozi, et al.
Publicado: (2023)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
por: Ma, Will, et al.
Publicado: (2024)

Matching and Edge Cover in Temporal Graphs
por: Cioni, Lapo, et al.
Publicado: (2025)

Packed Acyclic Deterministic Finite Automata
por: Shibata, Hiroki, et al.
Publicado: (2024)

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

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
por: Peng, Bo, et al.
Publicado: (2025)

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

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
por: Geng, Yutong, et al.
Publicado: (2025)

Deterministic Online Bipartite Edge Coloring
por: Blikstad, Joakim, et al.
Publicado: (2024)

Online Edge Coloring: Sharp Thresholds
por: Blikstad, Joakim, et al.
Publicado: (2025)

Online Matching: A Brief Survey
por: Huang, Zhiyi, et al.
Publicado: (2024)

On the Advice Complexity of Online Matching on the Line
por: Csaba, Béla, et al.
Publicado: (2024)

Partitioning Trillion Edge Graphs on Edge Devices
por: Chhabra, Adil, et al.
Publicado: (2024)

Algorithms for Optimizing Acyclic Queries
por: Luo, Zheng, et al.
Publicado: (2025)

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

Almost Tight Bounds for Online Hypergraph Matching
por: Tröbst, Thorben, et al.
Publicado: (2024)

Online Metric Matching: Beyond the Worst Case
por: Yang, Mingwei, et al.
Publicado: (2024)

Online Matching with Delays and Size-based Costs
por: Kawase, Yasushi, et al.
Publicado: (2024)

Edge-Weighted Online Bipartite Matching
por: Fahrbach, Matthew, et al.
Publicado: (2020)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
por: El-Hayek, Antoine, et al.
Publicado: (2023)

Enhanced Graph Pattern Matching
por: Cotumaccio, Nicola
Publicado: (2024)

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
por: Esposito, Emmanuel, et al.
Publicado: (2022)

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

Online Graph Embedding in Star Graphs
por: Dallot, Julien, et al.
Publicado: (2026)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
por: Yoshida, Yuichi
Publicado: (2026)

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

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

Graph Exploration with Edge Weight Estimates
por: Gehnen, Matthias, et al.
Publicado: (2025)