Dynamic Relaxations for Online Bipartite Matching

DOI10.1287/ijoc.2022.1168OpenAlexW2905815131MaRDI QIDQ5106387

Alejandro Toriello, Alfredo Torrico

Publication date: 19 September 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.01557

zbMATH Keywords

dynamic programmingonline matchingfacet-defining inequalitytime-indexed relaxations

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites Work

• Unnamed Item
• A polyhedral approach to online bipartite matching
• Online stochastic matching: new algorithms and bounds
• Combinatorial auctions with decreasing marginal utilities
• Linear Programming and Sequential Decisions
• An Analysis of Bid-Price Controls for Network Revenue Management
• Reductions of Approximate Linear Programs for Network Revenue Management
• On a Piecewise-Linear Approximation for Network Revenue Management
• Bayesian Mechanism Design
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• On the Approximate Linear Programming Approach for Network Revenue Management Problems
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• Dynamic Bid Prices in Revenue Management
• AdWords and generalized online matching
• Improved Bounds for Online Stochastic Matching
• A Characterization of Waiting Time Performance Realizable by Single-Server Queues
• Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems
• A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
• The NP-completeness column: An ongoing guide
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• Placement Optimization in Refugee Resettlement
• Online Stochastic Matching: Beating 1-1/e
• Online Stochastic Matching: New Algorithms with Better Bounds
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Online stochastic matching, poisson arrivals, and the natural linear program

This page was built for publication: Dynamic Relaxations for Online Bipartite Matching