Probabilistic Models and Algorithmic Analysis of Network Problems

Network-related problems span over many areas in computer science. In this dissertation, we investigate two problems, one is in the domain of distributed computing, and the other is in the domain of graph mining. We approach these problems by probabilistic tools, to model, analyze, and design algorithms. In the first problem, we aim to improve upon the known bounds of some fundamental distributed algorithms, Minimum Spanning Tree (MST) in particular. We propose the Smoothed Analysis, where the key is to randomly and slightly alter the input, and show new asymptotic bounds. For the MST problem, we also design an algorithm that almost matches the lower bound. In the second problem, we study influence spreading in networks, which is a stochastic process. We propose a new optimization problem: minimizing the seed set with probabilistic guarantees on the influence. This problem relates to non-submodular target functions, and is hard even for an approximation solution. We design an efficient algorithm using relaxed multi-criterial approximation and Monte Carlo sampling. We provide theoretically proven properties and supportive empirical results.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Houston

Year dc:date.issued

2019

Author dc:creator

• Pham, Nguyen Dinh 1981-

Advisor dc:contributor.advisor

• Pandurangan, Gopal

Committee members dc:contributor.committeemember

• Vullikanti, Anil
• Johnsson, Lennart
• Laszka, Aron

• Distributed computing
• Smoothed analysis
• Influence maximization
• Optimization

Statement dc:rights

• The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/10657/5571

OAI identifier oai:identifier

oai:uh-ir.tdl.org:10657/5571