Project Details
Funding Scheme : General Research Fund
Project Number : 17200214
Project Title(English) : Oblivious Matching Algorithms on Unknown (Hyper) Graphs  
Project Title(Chinese) : 未知(超)圖上的無識匹配算法 
Principal Investigator(English) : Dr Chan, Hubert Tsz Hong 
Principal Investigator(Chinese) :  
Department : Department of Computer Science
Institution : The University of Hong Kong
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2014 / 15
Fund Approved : 875,000
Project Status : On-going
Completion Date : 31-12-2017
Abstract as per original application
This project will investigate the classical maximum matching problem of finding a maximum subset of non-intersecting edges, in the case where the graph structure is unknown. The existence of an edge between two nodes remains unknown until the pair is probed; when an edge is found, the corresponding pair must be matched up and removed from the graph. Our goal is to investigate various versions of the problem, and design algorithms to maximize the size or the weight of the matching. The project will bring about technical breakthroughs, and the problem has real-world applications such as online advertising, online dating, and the kidney exchange problem. More specifically, in the oblivious matching problem, the graph is fixed in advance but unknown to the algorithm. The algorithm knows only the set of nodes, and specifies an order of node pairs to probe the graph. The performance ratio is the size of the matching produced to that of a maximum matching. A ratio of 0.5 can be achieved trivially and is tight for deterministic algorithms. Since the mid-1990s, theoreticians such as Fulkerson Prize winners Dyer and Frieze, and two-time Goedel Prize winner Szegedy used sophisticated arguments to prove that several randomized algorithms can achieve ratios marginally (around 0.004) above 0.5. In large-scale applications, this could mean a huge increase in utility. We will develop novel mathematical techniques to produce significant results. In our preliminary work, we use sophisticated combinatorial analysis and mathematical programming techniques to achieve the currently best proven ratio of 0.523. This is a major breakthrough, and provides an encouraging start for the design of algorithms for more general versions of the problem in which the nodes or edges of the graph are weighted. Our techniques also offer us important insights for investigating different versions of the problem on hypergraphs. For instance, the analogous result for 3-uniform hypergraphs would be breaking the 1/3 barrier. This has important application to combinatorial auctions under settings in which complete information is unavailable. In conclusion, there is no doubt that oblivious matching is an important problem for theoreticians and practitioners alike. The proposed project will bring new insights to the problem and the technological breakthroughs will have a significant impact on the wider theoretical community.
本項目將研究在未知圖結構情況下的經典最大匹配問題,即尋找最大不相交邊集合。一條邊存在與否只有當相應的點對被探測時才可獲知;當一條邊被探測並已知存在時,相應的點對必須被匹配並移出該圖。我們的目標是研究該問題的多個版本,並設計最大化匹配大小或權值的算法。本項目將帶來技術上的突破,並且該問題對在線廣告、在線約會及腎臟交換問題中具有實際應用。 具體地講,在該無識匹配問題中,所研究的圖已預先確定,但算法並不知道其結構。算法只知道該圖的點集合,並製定一個點對順序來探測該圖。性能比是指算法產生的匹配的大小與最大匹配大小之間的比值。簡單的算法即可獲得0.5的性能比,並且該數值對確定算法來說是緊緻的。從上世紀九十年代以來,包括Fulkerson獎獲得者Dyer和Frieze以及兩次哥德爾獎獲得者Szegedy在內的理論家,利用複雜的論證證明了某些隨機算法可以達到略微(幅度約0.004)大於0.5的性能比。在大規模應用中,這或許會帶來效用的巨大提升。 我們將開發全新的數學工具以獲得重大成果。在前期工作中,我們利用複雜的組合分析和數學規劃工具獲得了當前可被證明的最好性能比0.523。這是一個重大突破,並鼓勵我們開始針對帶權值點或帶權值邊等普適模型設計算法。 我們開發的工具也使我們對該問題在超圖上的各種版本有了重要的深刻的理解。例如,在3-均勻超圖上的類似結果將打破性能比1/3的壁壘。該結果在無法獲知全部信息情況下的組合拍賣問題中具有重要應用價值。
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted