Cover Image

A New Impossibility Result for Online Bipartite Matching Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chierichetti, Flavio, Giacchini, Mirko, Panconesi, Alessandro, Vattani, Andrea
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Multinomial Logits in $O(n \log n)$ time
by: Chierichetti, Flavio, et al.
Published: (2026)

On the LSH Distortion of Ulam and Cayley Similarities
by: Chierichetti, Flavio, et al.
Published: (2026)

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

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

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)

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

Optimal Rounding for Two-Stage Bipartite Matching
by: Pollner, Tristan, et al.
Published: (2025)

Interval-Constrained Bipartite Matching over Time
by: Abels, Andreas, et al.
Published: (2024)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

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

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

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

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

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

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

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

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Optimizing Inventory Placement for a Downstream Online Matching Problem
by: Epstein, Boris, et al.
Published: (2024)

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

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
by: Bernstein, Aaron, et al.
Published: (2025)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
by: Tang, Zhihao Gavin
Published: (2026)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

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

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

New Results on a General Class of Minimum Norm Optimization Problems
by: Chen, Kuowen, et al.
Published: (2025)

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

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

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

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

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

Bipartite Exact Matching in P
by: Du, Yuefeng
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)

The Online Submodular Cover Problem
by: Gupta, Anupam, et al.
Published: (2025)