大数据挖掘advertising.ppt

CS 345Data Mining
Online algorithms
Search advertising
Online algorithms
Classic model of algorithms
You get to see the entire input, pute some function of it
In this context, “offline algorithm”
Online algorithm
You get to see the input one piece at a time, and need to make irrevocable decisions along the way
Similar to data stream models
Example: Bipartite matching
1
2
3
4
a
b
c
d
Girls
Boys
Example: Bipartite matching
1
2
3
4
a
b
c
d
M = {(1,a),(2,b),(3,d)} is a matching
Cardinality of matching = |M| = 3
Girls
Boys
Example: Bipartite matching
1
2
3
4
a
b
c
d
Girls
Boys
M = {(1,c),(2,b),(3,d),(4,a)} is a
perfect matching
Matching Algorithm
Problem: Find a maximum-cardinality matching for a given bipartite graph
A perfect one if it exists
There is a polynomial-time offline algorithm (Hopcroft and Karp 1973)
But what if we don’t have the entire graph upfront?
Online problem
Initially, we are given the set Boys
In each round, one girl’s choices are revealed
At that time, we have to decide to either:
Pair the girl with a boy
Don’t pair the girl with any boy
Example of application: assigning tasks to servers
Online problem
1
2
3
4
a
b
c
d
(1,a)
(2,b)
(3,d)
Greedy algorithm
Pair the new girl with any eligible boy
If there is none, don’t pair girl
How good is the algorithm?
Competitive Ratio
For input I, suppose greedy produces matching Mgreedy while an optimal matching is Mopt
Competitive ratio =
minall possible inputs I (|Mgreedy|/|Mopt|)