A polyhedral approach to online bipartite matching
成果类型：
Article
署名作者：
Torrico, Alfredo; Ahmed, Shabbir; Toriello, Alejandro
署名单位：
University System of Georgia; Georgia Institute of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-017-1219-3
发表日期：
2018
页码：
443-465
关键词：
摘要：
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.
来源URL：