On Combinatorial and Stochastic Optimization

In this dissertation, we study four problems in computational and stochastic optimization. We design new algorithmic techniques, leading to improved algorithms for fundamental clustering and scheduling problems. The first two chapters give improved approximation algorithms for classic combinatorial optimization problems. The final two chapters consider combinatorial optimization under stochastic uncertainty. For these problems, we give improved approximations as well as characterize the power of adaptivity…