Cover Image

On the Advice Complexity of Online Matching on the Line

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Csaba, Béla, Nagy-György, Judit
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Advice Complexity of Online Unit Clustering
by: Nagy-György, Judit
Published: (2023)

Online Computation with Untrusted Advice
by: Angelopoulos, Spyros, et al.
Published: (2019)

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

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

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

Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
by: Jin, Billy, et al.
Published: (2022)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Constraint Satisfaction Problems with Advice
by: Ghoshal, Suprovat, et al.
Published: (2024)

Improving Online Bin Covering with Little Advice
by: Brodnik, Andrej, et al.
Published: (2025)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

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

Online Drone Coverage of Targets on a Line
by: Dobrev, Stefan, et al.
Published: (2026)

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

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

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

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)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

Semi-Robust Communication Complexity of Maximum Matching
by: Huete, Gabriel Cipriani, et al.
Published: (2025)

The Communication Complexity of Pattern Matching with Edits Revisited
by: Kociumaka, Tomasz, et al.
Published: (2026)

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

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Optimizing Inventory Placement for a Downstream Online Matching Problem
by: Epstein, Boris, 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)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

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

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

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

Complexity Classes for Online Problems with and without Predictions
by: Berg, Magnus, et al.
Published: (2024)

Learning-Augmented Online TRP on a Line
by: Guragain, Swapnil, et al.
Published: (2026)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
by: Canonne, Clément L., et al.
Published: (2025)

Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion
by: Li, Yingxi, et al.
Published: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Online Matching under KIID: Enhanced Competitive Analysis through Ordinary Differential Equation Systems
by: Xu, Pan
Published: (2025)

Online Resource Allocation with Convex-set Machine-Learned Advice
by: Golrezaei, Negin, et al.
Published: (2023)

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)

Online Matching on $3$-Uniform Hypergraphs
by: Borst, Sander, et al.
Published: (2024)