A polyhedral approach to online bipartite matching

DOI10.1007/s10107-017-1219-3zbMath1406.90109OpenAlexW2772076743MaRDI QIDQ1801015

Alejandro Toriello, Shabbir Ahmed, Alfredo Torrico

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1219-3

zbMATH Keywords

dynamic programonline matchingpolyhedral relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

Dynamic Relaxations for Online Bipartite Matching, Dynamic node packing

Cites Work

• Unnamed Item
• Generalized polynomial approximations in Markovian decision processes
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• Bayesian Mechanism Design
• On Circulant Matrices
• Online Stochastic Matching: Online Actions Based on Offline Statistics
• A Dynamic Traveling Salesman Problem with Stochastic Arc Costs
• Online Stochastic Weighted Matching: Improved Approximation Algorithms
• AdWords and generalized online matching
• Improved Bounds for Online Stochastic Matching
• The Linear Programming Approach to Approximate Dynamic Programming
• A Characterization of Waiting Time Performance Realizable by Single-Server Queues
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• A Unifying Approximate Dynamic Programming Model for the Economic Lot Scheduling Problem
• Online Stochastic Matching: Beating 1-1/e
• Online Stochastic Matching: New Algorithms with Better Bounds
• A Price-Directed Approach to Stochastic Inventory/Routing
• Online bipartite matching with random arrivals