Loading...
Loading...

Go to the content (press return)

On-line matching in regular bipartite graphs

Author
Barriere, E.; Muñoz, X.
Type of activity
Presentation of work at congresses
Name of edition
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...
Keywords
bipartite graph, matching, on-line algorithm, regular graph
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants