File Download
Supplementary

postgraduate thesis: Randomized algorithms for graph problems with incomplete information

TitleRandomized algorithms for graph problems with incomplete information
Authors
Issue Date2015
PublisherThe 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
AbstractI 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 PUSH-PULL 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 PA-graphs. 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 node-weighted version of the oblivious matching problem, each node of the graph has a non-negative 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 non-trivial performance ratio strictly above 0:5 for the node-weighted version of the problem.
DegreeDoctor of Philosophy
SubjectGraph theory - Data processing
Stochastic processes - Data processing
Algorithms
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/219980

 

DC FieldValueLanguage
dc.contributor.authorWu, Xiaowei-
dc.contributor.author吴晓伟-
dc.date.accessioned2015-10-08T23:12:16Z-
dc.date.available2015-10-08T23:12:16Z-
dc.date.issued2015-
dc.identifier.citationWu, 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.urihttp://hdl.handle.net/10722/219980-
dc.description.abstractI 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 PUSH-PULL 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 PA-graphs. 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 node-weighted version of the oblivious matching problem, each node of the graph has a non-negative 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 non-trivial performance ratio strictly above 0:5 for the node-weighted version of the problem.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshGraph theory - Data processing-
dc.subject.lcshStochastic processes - Data processing-
dc.subject.lcshAlgorithms-
dc.titleRandomized algorithms for graph problems with incomplete information-
dc.typePG_Thesis-
dc.identifier.hkulb5570808-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats