File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Randomized algorithms for graph problems with incomplete information
Title  Randomized algorithms for graph problems with incomplete information 

Authors  
Issue Date  2015 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Wu, X. [吴晓伟]. (2015). Randomized algorithms for graph problems with incomplete information. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5570808 
Abstract  I study several graph problems in which the information of the given graphs are incomplete. I devise randomized algorithms to solve those problems and provide theoretical analysis for their performances.
In the rumor spreading problem, a connected graph with n nodes is given and the objective is to spread a rumor, which is initiated by one node, to all nodes in the graph as fast as possible under distributed communication. I extend the classic PUSHPULL protocol to stream B rumors in a graph from a single source node to all nodes in the graph and show that perfect pipelining can be achieved with high probability in directed random graphs and PAgraphs.
Motivated by online advertisement and exchange settings, the oblivious matching problem aims at finding a maximum matching between nodes in a simple undirected graph whose edges are oblivious to the algorithm. An algorithm for the problem determines an ordering of all unordered pairs of nodes and tries to match the pairs greedily according to the ordering. While any greedy algorithm for the problem has performance ratio at least 0:5, no algorithm achieves performance ratio strictly above 0:5 until Aronson et al. proved that the Modified Randomized Greedy algorithm achieves a performance ratio 0:5 + 1/400000 on arbitrary graphs. I revisit the classic Ranking algorithm for the problem and derive a linear program, whose optimal solution provides a lower bound for the performance ratio, by analyzing the structural properties of the Ranking algorithm. I show that the Ranking algorithm has a performance ratio at least 0:523166, which is the optimal solution for our linear program. I later improve the performance ratio to 0:526823 by exploring more sophisticated properties of the Ranking algorithm.
In the nodeweighted version of the oblivious matching problem, each node of the graph has a nonnegative weight and the objective is to form a matching that maximizes the total weight of matched nodes. I provide a weighted version of the Ranking algorithm for this problem and show that its performance ratio is at least 0:501505, which is the first nontrivial performance ratio strictly above 0:5 for the nodeweighted version of the problem. 
Degree  Doctor of Philosophy 
Subject  Graph theory  Data processing Stochastic processes  Data processing Algorithms 
Dept/Program  Computer Science 
Persistent Identifier  http://hdl.handle.net/10722/219980 
HKU Library Item ID  b5570808 
DC Field  Value  Language 

dc.contributor.author  Wu, Xiaowei   
dc.contributor.author  吴晓伟   
dc.date.accessioned  20151008T23:12:16Z   
dc.date.available  20151008T23:12:16Z   
dc.date.issued  2015   
dc.identifier.citation  Wu, X. [吴晓伟]. (2015). Randomized algorithms for graph problems with incomplete information. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5570808   
dc.identifier.uri  http://hdl.handle.net/10722/219980   
dc.description.abstract  I study several graph problems in which the information of the given graphs are incomplete. I devise randomized algorithms to solve those problems and provide theoretical analysis for their performances. In the rumor spreading problem, a connected graph with n nodes is given and the objective is to spread a rumor, which is initiated by one node, to all nodes in the graph as fast as possible under distributed communication. I extend the classic PUSHPULL protocol to stream B rumors in a graph from a single source node to all nodes in the graph and show that perfect pipelining can be achieved with high probability in directed random graphs and PAgraphs. Motivated by online advertisement and exchange settings, the oblivious matching problem aims at finding a maximum matching between nodes in a simple undirected graph whose edges are oblivious to the algorithm. An algorithm for the problem determines an ordering of all unordered pairs of nodes and tries to match the pairs greedily according to the ordering. While any greedy algorithm for the problem has performance ratio at least 0:5, no algorithm achieves performance ratio strictly above 0:5 until Aronson et al. proved that the Modified Randomized Greedy algorithm achieves a performance ratio 0:5 + 1/400000 on arbitrary graphs. I revisit the classic Ranking algorithm for the problem and derive a linear program, whose optimal solution provides a lower bound for the performance ratio, by analyzing the structural properties of the Ranking algorithm. I show that the Ranking algorithm has a performance ratio at least 0:523166, which is the optimal solution for our linear program. I later improve the performance ratio to 0:526823 by exploring more sophisticated properties of the Ranking algorithm. In the nodeweighted version of the oblivious matching problem, each node of the graph has a nonnegative weight and the objective is to form a matching that maximizes the total weight of matched nodes. I provide a weighted version of the Ranking algorithm for this problem and show that its performance ratio is at least 0:501505, which is the first nontrivial performance ratio strictly above 0:5 for the nodeweighted version of the problem.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.subject.lcsh  Graph theory  Data processing   
dc.subject.lcsh  Stochastic processes  Data processing   
dc.subject.lcsh  Algorithms   
dc.title  Randomized algorithms for graph problems with incomplete information   
dc.type  PG_Thesis   
dc.identifier.hkul  b5570808   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Computer Science   
dc.description.nature  published_or_final_version   