Panigrahi, DebmalyaHaney, Samuel Mitchell2019-06-072019-06-072019https://hdl.handle.net/10161/18661<p>In this dissertation, we study algorithmic problems motivated by the optimization of networks under uncertainty.</p><p>We summarize our contributions:</p><p>\begin{itemize}</p><p>\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.</p><p> $k$-server is an example of a problem in an \emph{online setting}: the algorithm must make irrevocable decisions without knowledge of future inputs.</p><p> 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.</p><p> We give an $O(\log k)$-competitive randomized algorithm for this problem on a uniform metric.</p><p> We additionally study other, similar generalizations of $k$-server.</p><p>\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.</p><p> 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.</p><p>\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.</p><p> We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems.</p><p> 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.</p><p>\item \textbf{Multicast Games:}</p><p> We study the effect of strategic behavior on network design.</p><p> 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.</p><p> 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.</p><p> 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).</p><p> </p><p> We make progress towards a better price of stability bound for multicast games.</p><p>In particular, we show a constant upper bound on the PoS of multicast games for quasi-bipartite graphs. These are </p><p>graphs where all edges are between two terminals (as in broadcast games) or between a terminal and a </p><p>nonterminal, but there is no edge between nonterminals. This represents a natural class of intermediate </p><p>generality between broadcast and multicast games. </p><p>\end{itemize}</p>Computer scienceAlgorithmsTheoryDissertation