Show simple item record

dc.contributor.advisorMorton, David P.en
dc.contributor.advisorHasenbein, John J.en
dc.creatorLee, Jinho, doctor of operations research and industrial engineeringen
dc.date.accessioned2012-11-20T19:35:20Zen
dc.date.available2012-11-20T19:35:20Zen
dc.date.created2012-08en
dc.date.issued2012-11-20en
dc.date.submittedAugust 2012en
dc.identifier.urihttp://hdl.handle.net/2152/ETD-UT-2012-08-5924en
dc.descriptiontexten
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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoengen
dc.subjectSubmodularityen
dc.subjectGreedy heuristicen
dc.subjectDown-sampling procedureen
dc.subjectMonte Carlo approximationen
dc.titleStochastic Optimization Models for Rapid Detection of Viruses in Cellphone Networksen
dc.date.updated2012-11-20T19:35:29Zen
dc.identifier.slug2152/ETD-UT-2012-08-5924en
dc.contributor.committeeMemberPopova, Elmiraen
dc.contributor.committeeMemberKutanoglu, Erhanen
dc.contributor.committeeMemberShakkottai, Sanjayen
dc.description.departmentOperations Research and Industrial Engineeringen
dc.type.genrethesisen
thesis.degree.departmentOperations Research and Industrial Engineeringen
thesis.degree.disciplineOperations Research and Industrial Engineeringen
thesis.degree.grantorUniversity of Texas at Austinen
thesis.degree.levelDoctoralen
thesis.degree.nameDoctor of Philosophyen


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record