stanford大學-大數(shù)據(jù)挖掘-advertising-19-在線瀏覽
2025-02-09 18:45本頁面
【正文】 s Boys M = {(1,c),(2,b),(3,d),(4,a)} is a perfect matching Matching Algorithm ? Problem: Find a maximumcardinality matching for a given bipartite graph ? A perfect one if it exists ? There is a polynomialtime 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|) Analyzing the greedy algorithm ? Consider the set G of girls matched in Mopt but not in Mgreedy ? Then it must be the case that every boy adjacent to girls in G is already matched in Mgreedy ? There must be at least |G| such boys ? Otherwise the optimal algorithm could not have matched all the G girls ? Therefore |Mgreedy| 184。 |G| = |Mopt Mgreedy| |Mgreedy|/|Mopt| 184。 ? Simple analysis shows this is the worst case BALANCE algorithm [MSVV] ? [Mehta, Saberi, Vazirani, and Vazirani] ? For each query, pic
公司管理相關(guān)推薦
鄂ICP備17016276號-1