On the local level, we investigated the relationship between interaction and sequence evolution, functional class, phylogenetic class, and expression profiles. On the global level, we focused on large-scale properties like small-world, scale-free, and attack tolerance. Major differences were discovered between viral and cellular systems, and we were able to pinpoint directions for further investigation, both theoretically and experimentally. New approaches to discover functional associations through interaction patterns were also presented and validated.

To put the KSHV network in the context of host interactions, we were able to predict interactions between KSHV and human proteins and use them to connect the KSHV and human PPI networks. Though simulations, we show that the combined viral-host network is distinct from and superior to equivalent randomly combined networks. Our combined network provides the first-draft of a viral-host system, which is crucial to understanding viral pathogenicity.

Prior to generating the mesh we compute a mesh size function to specify the desired size of the elements. We have developed algorithms for automatic generation of size functions, adapted to the curvature and the feature size of the geometry. We propose a new method for limiting the gradients in the size function by solving a non-linear partial differential equation. We show that the solution to our gradient limiting equation is optimal for convex geometries, and we discuss efficient methods to solve it numerically.

Further, we consider optimization problems based on the shortest path metric and we find covering sets of size O(n^1+2/c log² n) that approximate the shortest path metric of a random vertex-induced subgraph with high probability. For edge-induced subgraphs, we prove a bound of O(n^1+2/c log n). The definition of our covering set is a strengthening of the notion of a c-spanner. It is known that a c-spanner may require n^1+1/c edges which is also a lower bound on our covering sets.

In the second part of the thesis, we turn to a model of stochastic optimization, where a solution is built sequentially by selecting a collection of items. We distinguish between adaptive and non-adaptive strategies, where adaptivity means being able to perceive the precise characteristics of chosen items and use this knowledge in subsequent decisions. The benefit of adaptivity is our central concept which we investigate for a variety of specific problems.

For the Stochastic Knapsack problem, we prove constant upper and lower bounds on the "adaptivity gap" between optimal adaptive and non-adaptive policies. For more general Stochastic Packing/Covering problems, we prove closely matching upper and lower bounds on the adaptivity gap as function of dimension d. An interesting feature of the results is that the adaptivity gap can be as large as the best polynomial-time approximation factor in the deterministic case. Yet, we can find a non-adaptive solution in polynomial time which has the same approximation guarantee with respect to the adaptive optimum.