Routing, disjoint paths, and classification.

摘要

In this thesis, we study three problems: routing, edge disjoint paths, and classification.; In hierarchical routing, we obtain "near-optimal" routing table size and path stretch through a randomized hierarchical decomposition scheme in the metric space induced by a graph. We say that a metric (X, d) has doubling dimension dim(X) at most alpha if every set of diameter D can be covered by 2alpha sets of diameter D/2. (A doubling metric is one whose doubling dimension dim(X) is a constant.) For a connected graph G, whose shortest path distances dG induce the doubling metric (X, dG), we show how to perform (1 + tau)-stretch routing on G for any 0 tau ≤ 1 with routing tables of size at most (alpha/tau) O(alpha) logDeltalogdelta bits with only (alpha/tau)O(alpha) logDelta entries, where Delta is the diameter of G and delta is the maximum degree of G.; The Edge Disjoint Paths (EDP) problem in undirected graphs refers to the following: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximability is not well understood. We show a polylogarithmic approximation algorithm for the undirected EDP problem in general graphs with a moderate restriction on graph connectivity: we require the global minimum cut of G to be O(log5 n). Our algorithm extends previous techniques in that it applies to graphs with high diameters and asymptotically large minors.; In the classification problem, we are given a set of 2N diploid individuals from population P1 and P2 (with no admixture), and a small amount of multilocus genotype data from the same set of K loci for all 2N individuals, and we aim to partition P 1 and P2 perfectly. In our model, given the population of origin of each individual, the genotypes are assumed to be generated by drawing alleles independently at random across the K loci, each form its own distribution. We show several results for this problem.