Optimization Online


A Polyhedral Approach to Online Bipartite Matching

Alfredo Torrico (atorrico3***at***gatech.edu)
Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Alejandro Toriello (atoriello***at***isye.gatech.edu)

Abstract: We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various relaxations of the polyhedral set of achievable matching probabilities, introduce valid inequalities, and discuss when they are facet-defining. We also show how several of these relaxations correspond to ranking policies and their time-dependent generalizations. We finally present a computational study of these relaxations and policies to determine their empirical performance.

Keywords: online matching, dynamic program, polyhedral relaxation

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Other Topics (Dynamic Programming )

Citation: Stewart School of Industrial and Systems Engineering, April, 2016

Download: [PDF]

Entry Submitted: 04/11/2016
Entry Accepted: 04/11/2016
Entry Last Modified: 07/12/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society