An Experimental Study of Algorithms for Online Bipartite Matching
From MaRDI portal
Abstract: We perform an experimental study of algorithms for online bipartite matching under the known i.i.d. input model with integral types. In the last decade, there has been substantial effort in designing complex algorithms with the goal of improving worst-case approximation ratios. Our goal is to determine how these algorithms perform on more practical instances rather than worst-case instances. In particular, we are interested in whether the ranking of the algorithms by their worst-case performance is consistent with the ranking of the algorithms by their average-case/practical performance. We are also interested in whether preprocessing times and implementation difficulties that are introduced by these algorithms are justified in practice. To that end we evaluate these algorithms on different random inputs as well as real-life instances obtained from publicly available repositories. We compare these algorithms against several simple greedy-style algorithms. Most of the complex algorithms in the literature are presented as being non-greedy (i.e., an algorithm can intentionally skip matching a node that has available neighbors) to simplify the analysis. Every such algorithm can be turned into a greedy one without hurting its worst-case performance. On our benchmarks, non-greedy versions of these algorithms perform much worse than their greedy versions. Greedy versions perform about as well as the simplest greedy algorithm by itself. This, together with our other findings, suggests that simplest greedy algorithms are competitive with the state-of-the-art worst-case algorithms for online bipartite matching on many average-case and practical input families. Greediness is by far the most important property of online algorithms for bipartite matching.
Recommendations
Cites work
- A critical point for random graphs with a given degree sequence
- Are stable instances easy?
- Dependent rounding and its applications to approximation algorithms
- Greedy bipartite matching in random type Poisson arrival model
- Heuristic initialization for bipartite matching problems
- scientific article; zbMATH DE number 5764830 (Why is no real title available?)
- Improved Bounds for Online Stochastic Matching
- New algorithms, better bounds, and a novel model for online stochastic matching
- On extensions of the deterministic online model for bipartite matching and max-sat
- On the power of advice and randomization for online bipartite matching
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Online matching and ad allocation
- Online Stochastic Matching: Beating 1-1/e
- Online stochastic matching: new algorithms with better bounds
- Power balance and apportionment algorithms for the United States Congress
- Power balance and apportionment algorithms for the United States Congress
- Random graph models of social networks
- Randomized primal-dual analysis of RANKING for online bipartite matching
Cited in
(5)- Learn from history for online bipartite matching
- A Polyhedral Approach to Online Bipartite Matching
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Online matching meets sampling without replacement
This page was built for publication: An Experimental Study of Algorithms for Online Bipartite Matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039931)
