UC Berkeley

In this dissertation, we study three NP-hard combinatorial optimization problems phrased on graphs. For each problem, we introduce one or more new algorithms tailored for the problem.

The first problem is the minimum k-terminal cut problem. Given a graph and a distinguished subset of vertices (``terminals''), we would like to remove the minimum weight set of edges that disconnect the terminals. We present a fixed-parameter-tractable branch-and-bound algorithm for the problem. We also show that (k-1)-stable instances of k-terminal cut can be solved optimally by calculating k-1 minimum isolating cuts: minimum cuts which separate one terminal from the rest. This analysis is tight: there exist (k-1-\epsilon)-stable instances for which the isolating cuts do not return the optimal solution.

The second problem concerns valid distance drawings of signed graphs. A valid distance drawing of a signed graph in R^k is an embedding of the graph in R^k such that, for every vertex, all its positive neighbors are closer than its negative neighbors. We address the question of finding L(n), the smallest dimension such that every signed graph with n nodes has a valid distance drawing in R^{L(n)}. In general, we show that \floor{\log_5(n-3) + 1} \leq L(n) \leq n-2. We introduce a new algorithm for computing L(n) and then compute L(n) exactly up to n=7. We offer a conjecture for the value of L(n) for all n.

The third problem is the maximum online perfect bipartite matching problem with i.i.d. arrivals. We introduce seven algorithms in two classes: three ``flow-guided'' algorithms and four ``evaluation-guided'' algorithms. Two of the evaluation-guided algorithms can be interpreted as derandomizations of flow-guided algorithms. We prove that at least three of the algorithms are 0.5-competitive, which is the best possible competitive ratio. The seven algorithms can be partially ordered: for some pairs, one may be expected to perform at least as well as the other on all instances. Through theoretical and empirical results, we determine all but four of the pairwise relations in this partial ordering.