Beta Online Matching

HUANG Xiao-yu; ZENG Qing-song; YANG Lei

doi:10.3969/j.issn.0372-2112.2017.05.033

您当前的位置：

首页 >

文章列表页 >

Beta Online Matching

更新时间：2025-07-16

- Beta Online Matching
- Acta Electronica Sinica Vol. 45, Issue 5, Pages: 1268-1271(2017)
- 作者机构：
  
  1. 华南理工大学经济与贸易学院,广东,广州,510006
  2. 广州番禺职业技术学院信息工程学院,广东,广州,511483
  3. 华南理工大学经济与贸易学院,广东,广州,510006
  4. 广州番禺职业技术学院信息工程学院,广东,广州,511483
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.05.033
  CLC： O212.3
- Published：2017
- 稿件说明：
移动端阅览
HUANG Xiao-yu, ZENG Qing-song, YANG Lei. Beta Online Matching[J]. Acta Electronica Sinica, 2017, 45(5): 1268-1271.
DOI：

HUANG Xiao-yu, ZENG Qing-song, YANG Lei. Beta Online Matching[J]. Acta Electronica Sinica, 2017, 45(5): 1268-1271. DOI： 10.3969/j.issn.0372-2112.2017.05.033.

摘要

二部图的在线匹配问题最早由Karp等人在1990年提出，该问题在近年得到了广泛的关注，在日常生活中有大量的应用.本文引入了

Beta

分布作为二部图节点间的邻接关系的统计先验，提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量，设计了在线匹配算法

Beta

OM，并证明了该算法的正确性.本文把

Beta

OM分别应用于基于人造数据和真实数据的在线匹配问题，实验的结果显示该算法优于经典的Greedy算法和Ranking算法.

Abstract

In recent years

the online bipartite graph matching problem has attracted substantial research attention as many real-life problems can be eventually reduced to it.In this work

we study the classic online matching problem that was initially investigated by Karp in 1990.We adopt the

Beta

distribution as the prior distribution of the adjacency relation among the nodes

and present a novel measure to evaluate the matching policy.We also design

Beta

distribution based online matching algorithm

and mathematically prove its soundness.Experiments with

Beta

OM as well as the benchmark algorithms on both synthetic and real data demonstrate that the proposed

Beta

OM is superior to the others.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimal Purchasing Strategy Based Risk Utility in Two Periods Inventory Systems under Stochastic Circumstance

A Social Network Recommendation Scheme Based on Bipartite Graph and Node Role Division

The Analysis of Convergence Rate of Individual COMID Iterates

EGSA:Extended Granular Computing-Based Software Architecture Model

A CFAR Detection Method of Ship Targets in Polarimetric SAR Imagery Based on Whitening Filter Under Beta Distributed Texture

Related Author

WU Xiao-hui

WU Cheng

ZHANG Long

SONG Shi-ji

LIU Yan-bing

LIU Han-song

XIAO Yun-peng

SHAO Yan-jian

Related Institution

Department of Automation,Tsinghua University

Chongqing Engineering Laboratory of Internet and Information Security, Chongqing University of Posts and Telecommunications

11th Department, Army Officer Academy of PLA

浙江大学计算机学院

株洲工学院计算机系

⁰