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 an underlying distribution, and must immediately be matched or discarded. We consider various relaxations of the set of achievable matching probabilities, introduce star inequalities and their generalizations, 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 results of a computational study of these relaxations and policies to determine their empirical performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adelman, D.: Price-directed replenishment of subsets: methodology and its application to inventory routing. Manuf. Serv. Oper. Manage. 5, 348–371 (2003)
Adelman, D.: A price-directed approach to stochastic inventory/routing. Oper. Res. 52, 499–514 (2004)
Adelman, D., Barz, C.: A unifying approximate dynamic programming model for the economic lot scheduling problem. Math. Oper. Res. 39, 374–402 (2014)
Bertsimas, D., Niño-Mora, J.: Conservation laws, extended polymatroids and multi-armed bandit problems; a polyhedral approach to indexable systems. Math. Oper. Res. 21, 257–306 (1996)
Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. ACM SIGACT News 39, 80–87 (2008)
Coffman Jr., E., Mitrani, I.: A characterization of waiting time performance realizable by single-server queues. Oper. Res. 28, 810–821 (1980)
de Farias, D., van Roy, B.: The linear programming approach to approximate dynamic programming. Oper. Res. 51, 850–865 (2003)
Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: beating \(1-1/e\). In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 117–126. IEEE (2009)
Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 170–181. Springer, Heidelberg (2011)
Jaillet, P., Lu, X.: Online stochastic matching: new algorithms with better bounds. Math. Oper. Res. 39, 624–646 (2014)
Karp, R., Vazirani, U., Vazirani, V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (STOC), pp. 352–358. ACM, New York (1990)
Kra, I., Simanca, S.: On circulant matrices. Not. AMS 59, 368–377 (2012)
Manshadi, V., Oveis Gharan, S., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37, 559–573 (2012)
Schweitzer, P., Seidmann, A.: Generalized polynomial approximations in markovian decision processes. J. Math. Anal. Appl. 110, 568–582 (1985)
Toriello, A.: Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem. Math. Program. 144, 247–264 (2014)
Toriello, A., Haskell, W., Poremba, M.: A dynamic traveling salesman problem with stochastic arc costs. Oper. Res. 62, 1107–1125 (2014)
Trick, M., Zin, S.: Spline approximations to value functions: a linear programming approach. Macroecon. Dyn. 1, 255–277 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Torrico, A., Ahmed, S., Toriello, A. (2016). A Polyhedral Approach to Online Bipartite Matching. In: Louveaux, Q., Skutella, M. (eds) Integer Programming and Combinatorial Optimization. IPCO 2016. Lecture Notes in Computer Science(), vol 9682. Springer, Cham. https://doi.org/10.1007/978-3-319-33461-5_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-33461-5_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-33460-8
Online ISBN: 978-3-319-33461-5
eBook Packages: Computer ScienceComputer Science (R0)