Algorithms for Networks With Uncertainty

In this dissertation, we study algorithmic problems motivated by the optimization of networks under uncertainty.

We summarize our contributions:

\begin{itemize}

\item \textbf{Subset $k$-server:} We propose and give algorithms for the \emph{all-or-one $k$-server}, a generalization of classical $k$-server problem.

$k$-server is an example of a problem in an \emph{online setting}: the algorithm must make irrevocable decisions without knowledge of future inputs.

In the all-or-one $k$-server generalization, clients can make a request for a particular server, or they can submit a general request that may be served by any server.

We give an $O(\log k)$-competitive randomized algorithm for this problem on a uniform metric.

We additionally study other, similar generalizations of $k$-server.

\item \textbf{Retraction:} Motivated by the problem of deploying distributed applications in the cloud, we initiate the algorithmic study of \emph{graph retraction} to a cycle, which seeks a mapping of a graph to a cycle in the graph so as to minimize the maximum stretch of any edge, subject to the constraint that each vertex in the cycle is mapped to itself.

Our main results are an $O(\min\{k, \sqrt{n}\})$-approximation for retracting any graph on $n$ nodes to a cycle with $k$ nodes, and an optimal algorithm when the graph is planar.

\item \textbf{Symmetric Interdiction:} We study the symmetric matching interdiction problem. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a $3/2$-approximation algorithm. We additionally introduce symmetric interdiction as a general model.

We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems.

We are motivated by applications in traffic engineering, where a network operator wishes to route traffic in a datacenter, but cannot distinguish between malicious and legitimate traffic.

\item \textbf{Multicast Games:}

We study the effect of strategic behavior on network design.

In \emph{multicast} and \emph{broadcast} games, agents in a graph attempt to connect to a \emph{root node} at minimum cost to themselves, sharing the cost of each edge along their path to the root equally with the other agents using the edge.

Such games can have many Nash equilibria, and networks formed dynamically by these agents could end up in any one of these equilibria, and may be very expensive.

The main open problem in this field has been to bound the ratio of least expensive Nash equilibrium to the least expensive network, called the price of stability (PoS).

We make progress towards a better price of stability bound for multicast games.

In particular, we show a constant upper bound on the PoS of multicast games for quasi-bipartite graphs. These are

graphs where all edges are between two terminals (as in broadcast games) or between a terminal and a

nonterminal, but there is no edge between nonterminals. This represents a natural class of intermediate

generality between broadcast and multicast games.

\end{itemize}