Show simple item record

dc.contributor.advisorHajiaghayi, MohammadTaghien_US
dc.contributor.authorDehghani, Sinaen_US
dc.date.accessioned2017-09-14T05:39:25Z
dc.date.available2017-09-14T05:39:25Z
dc.date.issued2017en_US
dc.identifierdoi:10.13016/M2DV1CP1C
dc.identifier.urihttp://hdl.handle.net/1903/19928
dc.description.abstractToday, computer and information networks play a significant role in the success of businesses, both large and small. Networks provide access to various services and resources to end users and devices. There has been extensive research on de- signing networks according to numerous criteria such as cost-efficiency, availability, adaptivity, survivability, among others. In this dissertation, we revisit some of the most fundamental network design problems in the presence of uncertainty. In most realistic models, we are forced to make decisions in the presence of an incomplete input, which is the source of uncertainty for an optimization algorithm. There are different types of uncertainty. For example, in stochastic settings, we may have some random variables derived from some known/unknown distributions. In online settings, the complete input is not known in a-priori and pieces of the input become available sequentially; leaving the algorithm to make decisions only with partial data. In this dissertation, we consider network design and network optimization problems with uncertainty. In particular, we study online bounded-degree Steiner network design, online survivable network design, and stochastic k-server. We analyze their complexity and design competitive algorithms for them.en_US
dc.language.isoenen_US
dc.titleOnline Network Design under Uncertaintyen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledk-serveren_US
dc.subject.pquncontrollednetwork designen_US
dc.subject.pquncontrolledonline algorithmsen_US
dc.subject.pquncontrolledSteiner networksen_US
dc.subject.pquncontrolleduncertaintyen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record