Buchumschlag

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Peng, Bo, Tang, Zhihao Gavin
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computer Science and Game Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
von: Tang, Zhihao Gavin
Veröffentlicht: (2026)

Edge-Weighted Online Bipartite Matching
von: Fahrbach, Matthew, et al.
Veröffentlicht: (2020)

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
von: Ezra, Tomer, et al.
Veröffentlicht: (2024)

Prophet Secretary and Matching: the Significance of the Largest Item
von: Chen, Ziyun, et al.
Veröffentlicht: (2024)

Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
von: Chen, Liyan, et al.
Veröffentlicht: (2024)

Online Coalition Formation under Random Arrival or Coalition Dissolution
von: Bullinger, Martin, et al.
Veröffentlicht: (2023)

Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three
von: Pashkovich, Kanstantsin, et al.
Veröffentlicht: (2026)

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare
von: Zargari, Faraz, et al.
Veröffentlicht: (2025)

Optimal Pricing with Unreliable Signals
von: Tang, Zhihao Gavin, et al.
Veröffentlicht: (2026)

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
von: Glitzner, Frederik, et al.
Veröffentlicht: (2025)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
von: Koenemann, Jochen, et al.
Veröffentlicht: (2021)

Fairness and Efficiency in Online Class Matching
von: Hajiaghayi, MohammadTaghi, et al.
Veröffentlicht: (2024)

Online Matching Meets Sampling Without Replacement
von: Huang, Zhiyi, et al.
Veröffentlicht: (2024)

Prophet Upper Bounds for Online Matching and Auctions
von: Soto, José, et al.
Veröffentlicht: (2024)

Truthful Matching with Online Items and Offline Agents
von: Feldman, Michal, et al.
Veröffentlicht: (2022)

Matching with Nested and Bundled Pandora Boxes
von: Bowers, Robin, et al.
Veröffentlicht: (2024)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
von: Borst, Sander, et al.
Veröffentlicht: (2026)

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP
von: Yan, Shuyi
Veröffentlicht: (2025)

EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
von: Afshinmehr, Mahyar, et al.
Veröffentlicht: (2024)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
von: Yan, Shuyi
Veröffentlicht: (2022)

Risk-Sensitive Online Selection with Bounded Adaptivity
von: Nekouyan, Hossein, et al.
Veröffentlicht: (2025)

Posted Price Mechanisms for Online Allocation with Diseconomies of Scale
von: Jazi, Hossein Nekouyan, et al.
Veröffentlicht: (2025)

Static Pricing for Online Selection Problem and its Variants
von: Sun, Bo, et al.
Veröffentlicht: (2024)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
von: Kevi, Eniko, et al.
Veröffentlicht: (2024)

Stable Matching with Interviews
von: Ashlagi, Itai, et al.
Veröffentlicht: (2025)

Robust Popular Matchings
von: Bullinger, Martin, et al.
Veröffentlicht: (2024)

Stable Matching with Deviators and Conformists
von: Glitzner, Frederik, et al.
Veröffentlicht: (2026)

Revisiting Fair and Efficient Allocations for Bivalued Goods
von: Liu, Hui, et al.
Veröffentlicht: (2026)

Stable Hypergraph Matching in Unimodular Hypergraphs
von: Biró, Péter, et al.
Veröffentlicht: (2025)

Online Job Assignment
von: Ekbatani, Farbod, et al.
Veröffentlicht: (2025)

Online Block Packing
von: Eliezer, Ariel Ben, et al.
Veröffentlicht: (2025)

Fairness and Efficiency in Two-Sided Matching Markets
von: Jain, Pallavi, et al.
Veröffentlicht: (2025)

Online Matroid Embeddings
von: Cristi, Andrés, et al.
Veröffentlicht: (2024)

Condorcet Dimension and Pareto Optimality for Matchings and Beyond
von: Kavitha, Telikepalli, et al.
Veröffentlicht: (2026)

Near-Feasible Stable Matchings: Incentives and Optimality
von: Glitzner, Frederik
Veröffentlicht: (2026)

A Minimax Perspective on Almost-Stable Matchings
von: Glitzner, Frederik, et al.
Veröffentlicht: (2026)

The Distortion of Prior-Independent b-Matching Mechanisms
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

Optimal Capacity Modification for Stable Matchings with Ties
von: Ranjan, Keshav, et al.
Veröffentlicht: (2024)

Approximating Nash Social Welfare by Matching and Local Search
von: Garg, Jugal, et al.
Veröffentlicht: (2022)

MATWA: A Web Toolkit for Matching under Preferences
von: Glitzner, Frederik, et al.
Veröffentlicht: (2024)