Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which we are given $m$ agents, $n$ indivisible resources, and we have to allocate resources in order to maximize the happiness of the least happy agent. For the network design part, we study two key problems: the Steiner Forest problem and the Matching Augmentation problem.In the first part of this thesis, we give improved guarantees for the Santa Claus problem in two prominent settings. First, we consider the Santa Claus problem in the setting where the happiness of each agent $i$ is an arbitrary linear function $f_i$. Obtaining a constant factor approximation in that setting is a major open problem in the area of approximation algorithms. In 2009, the MaxMin Arborescences problem was identified as a key special case that appears to capture most of the difficulty of the general problem. Even in that special case, a constant factor approximation has remained elusive, and the current best algorithm only guarantees a polylogarithmic approximation in quasi-polynomial time. We give an exponential improvement to this, an $O(\textrm{poly}(\log \log (n)))$-approximation in quasi-polynomial time for the MaxMin Arborescences problem.Our second result in this part considers the Santa Claus problem in the restricted assignment case: all the agents have the same happiness function $f$, but each agent $i$ is only interested in a subset $\Gamma_i$ of the resources. When $f$ is a monotone submodular function, we show that we can obtain an $O(\log \log n)$-approximation in polynomial time. Before our work, comparable results in this setting were only known for the case where $f$ is a linear function.In the second part of this thesis, we start with the Steiner Forest problem which is defined as follows. Given a graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k\}\}$, the goal is to return a minimum-weight subgraph that connects all the pairs. In 1996, Awerbuch, Azar, and Bartal showed that an intuitive greedy algorithm guarantees an $O(\log^2 k)$-approximation. Our first result is to show that, in fact, the greedy algorithm guarantees an $O(\log (k)\cdot \log \log (k))$-approximation, which is nearly tight in light of a known lower bound of order $\Omega(\log k)$. Interestingly, our analysis also gives important insights in the online setting of the problem, in which the pairs are revealed one by one in an adversarial order.Our last result is on the Matching Augmentation problem, a key problem to compute cheap $2$-edge connected subgraphs. We give a simple polynomial time algorithm that guarantees a better-than-$2$ approximation when compared to the standard relaxation of the problem known as the cut LP. In contrast, previous better-than-$2$ approximations were much more complicated and did not compare to this simple relaxation.