Show simple item record

dc.creatorLee, Jinho, doctor of operations research and industrial engineering
dc.date.accessioned2012-11-20T19:35:20Z
dc.date.available2012-11-20T19:35:20Z
dc.date.created2012-08
dc.date.issued2012-11-20
dc.date.submittedAugust 2012
dc.identifier.urihttp://hdl.handle.net/2152/ETD-UT-2012-08-5924
dc.descriptiontext
dc.description.abstractWe develop a class of models to represent the dynamics of a virus spreading in a cellphone network, employing a taxonomy that includes five key characteristics. Based on the resulting dynamics governing the spread, we present optimization models to rapidly detect the virus, subject to resource limitations. We consider two goals, maximizing the probability of detecting a virus by a time threshold and minimizing the expected time to detection, which can be applied to all spread models we consider. We establish a submodularity result for these two objective functions that ensures that a greedy heuristic yields a well-known constant-factor (63%) approximation. We relate the latter optimization problem, under a specific virus-spread mechanism from our class of models, to a classic facility-location model. Using data from a large carrier, we build several base cellphone contact networks of different scale. We then rescale these base networks using the so-called c-core decomposition that removes vertices of low degree in a recursive way. We further show that this down-sampling strategy preserves, in general, the topological properties of the base networks, based on testing several measures. For the objective that maximizes the probability that we detect a virus by a time threshold, we provide a sample-average optimization model that yields an asymptotically-optimal design for locating the detection devices, as the number of samples grows large. To choose a relevant time threshold, we perform a simulation for some spread models. We then test the performance of our proposed solution methods by solving the presented optimization models for some spread dynamics using some of the contact networks built after the c-core decomposition. The computational results show that the greedy algorithm is an efficient way to solve the corresponding sample-average approximation model, and the greedy solutions outperform some other simple solution approaches.
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.subjectSubmodularity
dc.subjectGreedy heuristic
dc.subjectDown-sampling procedure
dc.subjectMonte Carlo approximation
dc.titleStochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networks
dc.date.updated2012-11-20T19:35:29Z
dc.identifier.slug2152/ETD-UT-2012-08-5924
dc.description.departmentOperations Research and Industrial Engineering
dc.type.genrethesis*
thesis.degree.departmentOperations Research and Industrial Engineering
thesis.degree.disciplineOperations Research and Industrial Engineering
thesis.degree.grantorUniversity of Texas at Austin
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record