Randomized algorithms for graph problems with incomplete information

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 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.