Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

20171

Settings

Author: search.filters.author.Dehghani, SinaSubject: search.filters.subject.online algorithms

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Online Network Design under Uncertainty
    (2017) Dehghani, Sina; Hajiaghayi, MohammadTaghi; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Today, 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.