22nd International Colloquium on Structural Information and Communication Complexity
Date of publication
2015
Presentation's date
2015-07-16
Abstract
In an online problem, the input is revealed one step at a time. At every step, the online algorithm has to produce part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to a non optimal solution. The quality of an online algorithm is measured by its competitive ratio, which compares its performance with that of an optimal offline algorithm.
The online bipartite matching problem has been studied since a first paper...
In an online problem, the input is revealed one step at a time. At every step, the online algorithm has to produce part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to a non optimal solution. The quality of an online algorithm is measured by its competitive ratio, which compares its performance with that of an optimal offline algorithm.
The online bipartite matching problem has been studied since a first paper by Karp, Vazirani and Vazirani in 1990. In this poster we focus on the particular case of bipartite matching in regular graphs.
We found an upper bound of the competitive ratio for the online deterministic bipartite matching problem for regular graphs and described an algorithm for this problem. We conjecture that our algorithm matches the upper bound.