Can I read An Experimental Study of Algorithms for Online Bipartite Matching on EtoBox?

An Experimental Study of Algorithms for Online Bipartite Matching by Allan Borodin; Christodoulos Karavasilis; Denis Pankratov is a Computer Science article available to read on EtoBox.

What is An Experimental Study of Algorithms for Online Bipartite Matching about?

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 to improve 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

Who reads An Experimental Study of Algorithms for Online Bipartite Matching?

Author

Allan Borodin; Christodoulos Karavasilis; Denis Pankratov

Publisher

ACM

Published

2020

Language

EN

Field

Computer Science (Physical Sciences)