Cover Image

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Burathep, Kunanon, Erlebach, Thomas, Moses Jr, William K.
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Online Learning in the Random Order Model
by: Bernasconi, Martino, et al.
Published: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

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

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
by: Dogeas, Konstantinos, et al.
Published: (2023)

PAC Learning is just Bipartite Matching (Sort of)
by: Dughmi, Shaddin
Published: (2025)

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

Transductive and Learning-Augmented Online Regression
by: Raman, Vinod, 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)

Learning-Augmented Online Scheduling with Parsimonious Preemption
by: Blue, Mugen, et al.
Published: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
by: Lechowicz, Adam, et al.
Published: (2023)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
by: Sakaue, Shinsaku, et al.
Published: (2026)

Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
by: Gaitonde, Jason, et al.
Published: (2024)

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

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Degree-bounded Online Bipartite Matching: OCS vs. Ranking
by: Feng, Yilong, et al.
Published: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
by: Chierichetti, Flavio, et al.
Published: (2025)

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

Learning-Augmented Moment Estimation on Time-Decay Models
by: Nagawanshi, Soham, et al.
Published: (2026)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

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

Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line
by: Kuo, Tung-Wei
Published: (2024)

When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching
by: Udwani, Rajan
Published: (2023)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Learning-Augmented Hierarchical Clustering
by: Braverman, Vladimir, et al.
Published: (2025)

Learning-Augmented Frequent Directions
by: Aamand, Anders, et al.
Published: (2025)

Robust Learning-Augmented Dictionaries
by: Zeynali, Ali, et al.
Published: (2024)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Learning Augmented Graph $k$-Clustering
by: Fan, Chenglin, et al.
Published: (2025)

On the Power of Learning-Augmented Search Trees
by: Chen, Jingbang, et al.
Published: (2022)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)

Learning-Augmented Search Data Structures
by: Fu, Chunkai, et al.
Published: (2024)

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
by: Veldt, Nate, et al.
Published: (2026)

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

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
by: Erlebach, Thomas, et al.
Published: (2026)

Learning-Augmented Streaming Algorithms for Correlation Clustering
by: Dong, Yinhao, et al.
Published: (2025)

Prediction-Specific Design of Learning-Augmented Algorithms
by: Li, Sizhe, et al.
Published: (2025)

Towards Optimal Robustness in Learning-Augmented Paging
by: Chen, Peng, et al.
Published: (2026)