文档介绍：CS345 DataMiningOnlinealgorithmsSearchadvertisingOnlinealgorithmsClassicmodelofalgorithmsYougettoseetheentireinput,putesomefunctionofitInthiscontext,“offlinealgorithm”OnlinealgorithmYougettoseetheinputonepieceatatime,andneedtomakeirrevocabledecisionsalongthewayHowisthisdifferentfromthedatastreammodel?Example:Bipartitematching1234abcdGirlsBoysExample:Bipartitematching1234abcdM={(1,a),(2,b),(3,d)}isamatchingCardinalityofmatching=|M|=3GirlsBoysExample:Bipartitematching1234abcdGirlsBoysM={(1,c),(2,b),(3,d),(4,a)}isaperfectmatchingMatchingAlgorithmProblem:Findamaximum-cardinalitymatchingAperfectoneifitexistsThereisapolynomial-timeofflinealgorithm(HopcroftandKarp1973)Butwhatifwedon’thavetheentiregraphupfront?OnlineproblemInitially,wearegiventhesetBoysIneachround,onegirl’schoicesarerevealedAtthattime,wehavetodecidetoeither:PairthegirlwithaboyDon’tpairthegirlwithanyboyExampleofapplication:assigningtaskstoserversOnlineproblem1234abcd(1,a)(2,b)(3,d)GreedyalgorithmPairthenewgirlwithanyeligibleboyIfthereisnone,don’petitiveRatioForinputI,petitiveratio= minallpossibleinputsI(|Mgreedy|/|Mopt|)