Beta在线匹配

mutougeda

Beta在线匹配

摘要:二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法 BetaOM,并证明了该算法的正确性.本文把BetaOM 分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.
7 f' q6 {# o8 B- k关键词:二部图;在线匹配;Beta分布;随机优化
- b2 X7 ?, r0 D* X
6 `3 o0 I$ ]: ^1 `) |1引言
0 g6 j" p! l- U7 w9 J本文研究如下的二部图在线匹配问题:考察两个互不相交的节点集合s = { s, , s2 ,…" , s。}和T =  t , t2，…,t。} ,其中S为给定集合,它的每个成员节点最多只能与一个T中的节点发生匹配;T中的节点依下标递增序顺次到达,每个节点t,在抵达的同时还将揭示一个由S中所有和它相邻的节点构成的集合N, ,若N,中存在不少于一个可用的节点,则我们从这些节点中选择一个与t, 匹配,并称与t,的匹配是“成功”的,反之,则称该匹配为“失败”的.我们的任务是要设计一个合适的匹配策略T,使之能为每个新来的节点t, ,选出合适的节点s ,与之相配,使得在所有匹配完成后,累计的成功匹配数目达到最大.我们强调在上述设置中,T从每个N, 中选择的是“可用的”节点,原因在于,在由S、T中的所有节点构成的完整二部图中,每个s节点都可以同时与T中多个不同的节点相邻,因而相应的,它也可以出现在多个不同的邻接集合Ⅳ中.但注意节点s的实际匹配次数不能大于1 ,所以,对每个节点t, ,lN, l >0并不等价于N,中存在可用的s节点.
本文的研究属于经典的二部图在线匹配问题,对该问题的研究最早可以追溯到1990年Karp等人的工作".近20年来,研究者陆续提出了该问题的多种变体,如 b-Matching[2. 、 Adwords[3以及其它扩展["]等.但需要指出的是,这些扩展的求解策略多数仍然植根于文献[1]中提出的 Ranking 算法.事实上,对文献[2~4]，当它们研究的问题退化为与文献[1]相同的设置时,相应的求解策略也都与文献[1]中提出的 Ranking 算法等价[5.
, R1 w9 V; e+ F  `/ k当前,在对在线匹配算法的研究中,一个重要的特
2 Y- s# {, f* h( C, n6 J

游客，如果您要查看本帖隐藏内容请回复

: `# B* g) d4 O

2 K5 Y( ~: h+ `2 P( K

regngfpcb

Beta在线匹配