Motivation. Suppose you are Google. Many advertisers come to you and want to advertise on google searches by users. Now, users come it throughout the day, one by one, searching for whatever they want to search. You can show them one advertisement. How do you maximize the advertisement to show to the users?

def. Optimal Online Matching Algorithm. The optimal algorithm is just one that knows in advance what all users will search, and thus simply finds a maximum partition matching.

Whole Online Matching

def. Greedy Online Matching algorithm. When a new user from comes in and declares its edges, it simply matches to any valid advertiser .

  • This simply finds the maximal (not maximum) matching.
  • This is in the worst case two times worse than optimal online matching. Proof:
    1. When a new edge comes available, matching it to the “wrong” vertex will at most block two “correct matchings” (from optimal).
    2. Therefore

Fractional Online Matching

We may sometimes allow for fractional matchings, i.e. consider an edge “full” at weight , but the weight can be anywhere from . We still benchmark fractional online matching with the original optimal whole matching algorithm.

def. Greedy Fractional Online Matching Algorithm. let encountering edges. For every unfilled edge, equally fill to each. This algorithm is pretty bad. Consider the following worst case scenario:

  • Each set have verticies
  • Appears in order:
  • which matches all of to , and all of to .
  • For :
    • consider the time when is matching:
      • equally gives to all of s and .
      • This happens for ever , i.e. times
      • After the last vertex in , total finishes matching, all of have filled .
    • Now, each of only has of to match with.
    • Total fully matches , and of . Thus
  • Thus . Pretty bad. def. Water-filling Algorithm. The algorithm works like this: for every that appears, it outputs water at a constant rate. Fill the vertices with least water first at equal rate: In the example above of the worst-case greedy algorithm, water-filing does a better job. First consider filling and all of .
  • is already filled up to level (we know they are all filled up to equal amounts, because and are fully connected.)
  • is empty because it is only connected to
  • Total water output by is .
  • Total verticies.
  • We know that water level will rise above for everybody (until some ) because can’t hold that much Then, denoting the rate of water output by as :

Then, let be the height of water on after are done filling. Summing this up for all from and :

And then the remaining for each will be matched to . Total matched is:

(Note that we still compare with whole matching optimum.)

def. Ranking Algorithm.

def. Bid Scaling Algorithm.