{'fraction_non_alphanumeric': 0.018454935622317595, 'fraction_numerical': 0.0, 'mean_word_length': 5.249329758713137, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximation algorithms for network design with uncertainty

Network design problems model many naturally-arising problems that we would like to solve, including the Steiner tree problem and the k -median problem. Many of these problems are inherently N P-hard, and thus are often approached via approximation algorithms, which produce feasible solutions in polynomial time with provable guarantees about the solution quality. Until recently, solutions for these types of problems have focused on deterministic cases where the input to the problem is known. Yet, in many realistic problems that we encounter, there are issues of uncertainty in the input; in particular, demands for these network design problems may vary or be unknown. 
In this thesis, we provide approximation algorithms for a number of problems where there is uncertainty in the input. In the leasing model we are able to lease elements for various durations, which allows our solutions to benefit from natural economies of scale in the pricing of leases as well as correlation in demand patterns over time. We show a somewhat surprising connection between a class of deterministic, offline leasing problems and the corresponding multi-stage stochastic problems. This reduction permits us to use existing and newly derived results for stochastic optimization to provide approximation algorithms for a number of offline leasing problems. We then consider leasing problems in online models, both where we have stochastic information about the input stream but must make decisions online, as well as the classical adversarial model for online algorithms. 
Another form of uncertainty in the input occurs where all of the potential demands are known, but the specific set is not revealed to us. We study location problems where we are provided with scenarios, perhaps with associated probabilities of occurrence. Our goal is to either minimize the maximum cost over all realizable scenarios (the robust version), or minimize the expected cost using the probabilities (the stochastic version). For location problems that satisfy certain technical conditions (such as the k-median problem, as well as its capacitated and fault-tolerant versions), we provide a general framework to get logarithmic approximation guarantees for both the robust and stochastic versions.