Probabilistic Models and Algorithmic Analysis of Network Problems

Simple item page
dc.contributor.advisorPandurangan, Gopal
dc.contributor.committeeMemberVullikanti, Anil
dc.contributor.committeeMemberJohnsson, Lennart
dc.contributor.committeeMemberLaszka, Aron
dc.creatorPham, Nguyen Dinh 1981-
dc.date.accessioned2019-12-17T04:06:03Z
dc.date.createdDecember 2019
dc.date.issued2019-12
dc.date.submittedDecember 2019
dc.date.updated2019-12-17T04:06:03Z
dc.description.abstractNetwork-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.
dc.description.departmentComputer Science, Department of
dc.format.digitalOriginborn digital
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10657/5571
dc.language.isoeng
dc.rightsThe 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).
dc.subjectDistributed computing
dc.subjectSmoothed analysis
dc.subjectInfluence maximization
dc.subjectOptimization
dc.titleProbabilistic Models and Algorithmic Analysis of Network Problems
dc.type.dcmiText
dc.type.genreThesis
local.embargo.lift2021-12-01
local.embargo.terms2021-12-01
thesis.degree.collegeCollege of Natural Sciences and Mathematics
thesis.degree.departmentComputer Science, Department of
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Houston
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
PHAM-DISSERTATION-2019.pdf
Size:
616.02 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.43 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.81 KB
Format:
Plain Text
Description:
Download

Collections

Published ETD Collection