A polyhedral approach to online bipartite matching

DOI10.1007/S10107-017-1219-3zbMATH Open1406.90109OpenAlexW2772076743MaRDI QIDQ1801015FDOQ1801015

Authors: Alfredo Torrico, S. Ahmed, Alejandro Toriello 

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

Recommendations

• A Polyhedral Approach to Online Bipartite Matching
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• New algorithms, better bounds, and a novel model for online stochastic matching
• Online stochastic matching: new algorithms and bounds

zbMATH Keywords

dynamic programonline matchingpolyhedral relaxation

Mathematics Subject Classification ID

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

Cites Work

• Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
• AdWords and generalized online matching
• The Linear Programming Approach to Approximate Dynamic Programming
• A unifying approximate dynamic programming model for the economic lot scheduling problem
• Title not available (Why is that?)
• Improved Bounds for Online Stochastic Matching
• Online Stochastic Matching: Beating 1-1/e
• Online stochastic matching: new algorithms with better bounds
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Generalized polynomial approximations in Markovian decision processes
• A Price-Directed Approach to Stochastic Inventory/Routing
• Online matching and ad allocation
• On circulant matrices
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• A dynamic traveling salesman problem with stochastic arc costs
• Online stochastic weighted matching: improved approximation algorithms
• A Characterization of Waiting Time Performance Realizable by Single-Server Queues
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

Cited In (6)

• Dynamic node packing
• Dynamic Relaxations for Online Bipartite Matching
• Online total bipartite matching problem
• A polynomial algorithm for b-matchings: An alternative approach
• A Polyhedral Approach to Online Bipartite Matching
• Title not available (Why is that?)

This page was built for publication: A polyhedral approach to online bipartite matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801015)