CS 345Data Mining.ppt


文档分类:IT计算机 | 页数:约34页 举报非法文档有奖
1/34
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/34
文档列表 文档介绍
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|)

CS 345Data Mining 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数34
  • 收藏数0 收藏
  • 顶次数0
  • 上传人陈潇睡不醒
  • 文件大小375 KB
  • 时间2019-11-15