Approximation Algorithms for Network Design and Orienteering

This thesis presents approximation algorithms for some NP-Hard combinatorial optimization problems on graphs and networks; in particular, we study problems related to Network Design. Under the widely-believed complexity-theoretic assumption that P is not equal to NP, there are no efficient (i.e., polynomial-time) algorithms that solve these problems exactly. Hence, if one desires efficient algorithms for such problems, it is necessary to consider approximate solutions: An approximation algorithm for an NP-Hard problem is a polynomial time algorithm which, for any instance of the problem, finds a solution whose value is guaranteed to be within a multiplicative factor of the value of an optimal solution to that instance. We attempt to design algorithms for which this factor, referred to as the approximation ratio of the algorithm, is as small as possible. The field of Network Design comprises a large class of problems that deal with constructing networks of low cost and/or high capacity, routing data through existing networks, and many related issues. In this thesis, we focus chiefly on designing fault-tolerant networks. Two vertices u,v in a network are said to be k-edge-connected if deleting any set of k − 1 edges leaves u and v connected; similarly, they are k-vertex connected if deleting any set of k − 1 other vertices or edges leaves u and v connected. We focus on building networks that are highly connected, meaning that even if a small number of edges and nodes fail, the remaining nodes will still be able to communicate. A brief description of some of our results is given below. We study the problem of building 2-vertex-connected networks that are large and have low cost. Given an n-node graph with costs on its edges and any integer k, we give an O(log n log k) approximation for the problem of finding a minimum-cost 2-vertex-connected subgraph containing at least k nodes. We also give an algorithm of similar approximation ratio for maximizing the number of nodes in a 2-vertex-connected subgraph subject to a budget constraint on the total cost of its edges. Our algorithms are based on a pruning process that, given a 2-vertex-connected graph, finds a 2-vertex-connected subgraph of any desired size and of density comparable to the input graph, where the density of a graph is the ratio of its cost to the number of vertices it contains. This pruning algorithm is simple and efficient, and is likely to find additional applications. Recent breakthroughs on vertex-connectivity have made use of algorithms for element-connectivity problems. We develop an algorithm that, given a graph with some vertices marked as terminals, significantly simplifies the graph while preserving the pairwise element-connectivity of all terminals; in fact, the resulting graph is bipartite. We believe that our simplification/reduction algorithm will be a useful tool in many settings. We illustrate its applicability by giving algorithms to find many trees that each span a given terminal set, while being disjoint on edges and non-terminal vertices; such problems have applications in VLSI design and other areas. We also use this reduction algorithm to analyze simple algorithms for single-sink network design problems with high vertex-connectivity requirements; we give an O(k log n)-approximation for the problem of k-connecting a given set of terminals to a common sink. We study similar problems in which different types of links, of varying capacities and costs, can be used to connect nodes; assuming there are economies of scale, we give algorithms to construct low-cost networks with sufficient capacity or bandwidth to simultaneously support flow from each terminal to the common sink along many vertex-disjoint paths. We further investigate capacitated network design, where edges may have arbitrary costs and capacities. Given a connectivity requirement R_uv for each pair of vertices u,v, the goal is to find a low-cost network which, for each uv, can support a flow of R_uv units of traffic between u and v. We study several special cases of this problem, giving both algorithmic and hardness results. In addition to Network Design, we consider certain Traveling Salesperson-like problems, where the goal is to find short walks that visit many distinct vertices. We give a (2 + epsilon)-approximation for Orienteering in undirected graphs, achieving the best known approximation ratio, and the first approximation algorithm for Orienteering in directed graphs. We also give improved algorithms for Orienteering with time windows, in which vertices must be visited between specified release times and deadlines, and other related problems. These problems are motivated by applications in the fields of vehicle routing, delivery and transportation of goods, and robot path planning.

Size effects on self-assembly and melting of silver-alkanethiolate on inert surfaces

Self-assembled materials produced in the reaction between alkanethiol and Ag are characterized and compared. It is revealed that the size of the Ag substrate has a significant role in the self-assembly process and determines the reaction products. Alkanethiol adsorbs on the surface of Ag continuous planar thin films and only forms self-assembled monolayers (SAMs), while the reaction between alkanethiol and Ag clusters on inert surfaces is more aggressive and generates a significantly larger amount of alkanethiolate. Two dissimilar products are yielded depending on the size of the clusters. Small Ag clusters are more likely to be converted into multilayer silver-alkanethiolate (AgSR, R = CnH2n+1) crystals, while larger Ag clusters form monolayer-protected clusters (MPCs). The AgSR crystals are initially small and can ripen into large lamellae during thermal annealing. The crystals have facets and flat terraces with extended area, and have a strong preferred orientation in parallel with the substrate surface. The MPCs move laterally upon annealing and reorganize into a single-layer network with their separation distance approximately equal to the length of an extended alkyl chain. AgSR lamellar crystals grown on inert surfaces provide an excellent platform to study the melting characteristics of crystalline lamellae of polymeric materials with the thickness in the nanometer scale. This system is also unique in that each crystal has integer number of layers – magic-number size (thickness). The size of the crystals is controlled by adjusting the amount of Ag and the annealing temperature. X-ray diffraction (XRD) and atomic force microscopy (AFM) are combined to accurately determine the size (number of layers) of the lamellar crystals. The melting characteristics are measured with nanocalorimetry and show discrete melting transitions which are attributed to the magic-number sizes of the lamellar crystals. The discrete melting temperatures are intrinsic properties of the crystals with particular sizes. Smaller lamellar crystals with less number of layers melt at lower temperatures. The melting point depression is inversely proportional to the total thickness of the lamellae – the product of the number of layers and the layer thickness.