0
$\begingroup$

I was reading about online algorithms and bipartite matching.

I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf

But there's one part that I don't understand.

In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once

While I can see how such case if frequent in real life, I fail to understand what kind of implementation could be used to demonstrate this...

I thought of the following

  • Create a graph with girls
  • add boys and define manually the girls they like via some sort of user input (input py/cin c++)
  • solve(match) for the newly added boy according to rank(priority) and return to user input till no more girls are left or till user decides to stop?

In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls?

Is my suggestion correct? or did I misunderstand something?

Thanks in advance

$\endgroup$
1
$\begingroup$

Just to clarify your doubt. An online algorithm is an algorithm that does not have the whole input (otherwise it would be offline), but it gets the input in a sequential manner. Looking at your paper, for example, they define an online algorithm as (1 Introduction):

An on-line algorithm receives a sequence of requests and must respond to each request as soon as it is received

I would use a simpler example than a graph of boys and girls. Think about a list of numbers that you want to sort.

Then an offline algorithm would take the whole input and sort it: quicksort.

An online algorithm sorts after every single number, or better, it ensures that a certain property is maintained over a sequential input. An clear example of it is Insertion Sort, since it ensures that the output list is always sorted.

Now looking at your questions:

  1. In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once. ~> Exactly. The girls in the example arrive one by one. You might know how many they are in total, (since |V| seems to be given), but you do not know which one is the next one until you "matched" the current one. As in the "insertion sort" example, you do not know the next number until you sorted the current one.
  2. In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls? ~> The paper says "Let G(U,V,E) be a bipartite graph", therefore my take on it is that you know how many boys (|U|) and how many girls you have (|V|).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.