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.

Shape and chemically anisotropic colloidal particles: A theoretical study of their structure, phase behavior, and slow dynamics

A detailed non-equilibrium state diagram of shape-anisotropic particle fluids is constructed. The effects of particle shape are explored using Naive Mode Coupling Theory (NMCT), and a single particle Non-linear Langevin Equation (NLE) theory. The dynamical behavior of non-ergodic fluids are discussed. We employ a rotationally frozen approach to NMCT in order to determine a transition to center of mass (translational) localization. Both ideal and kinetic glass transitions are found to be highly shape dependent, and uniformly increase with particle dimensionality. The glass transition volume fraction of quasi 1- and 2- dimensional particles fall monotonically with the number of sites (aspect ratio), while 3-dimensional particles display a non-monotonic dependence of glassy vitrification on the number of sites. Introducing interparticle attractions results in a far more complex state diagram. The ideal non-ergodic boundary shows a glass-fluid-gel re-entrance previously predicted for spherical particle fluids. The non-ergodic region of the state diagram presents qualitatively different dynamics in different regimes. They are qualified by the different behaviors of the NLE dynamic free energy. The caging dominated, repulsive glass regime is characterized by long localization lengths and barrier locations, dictated by repulsive hard core interactions, while the bonding dominated gel region has short localization lengths (commensurate with the attraction range), and barrier locations. There exists a small region of the state diagram which is qualified by both glassy and gel localization lengths in the dynamic free energy. A much larger (high volume fraction, and high attraction strength) region of phase space is characterized by short gel-like localization lengths, and long barrier locations. The region is called the attractive glass and represents a 2-step relaxation process whereby a particle first breaks attractive physical bonds, and then escapes its topological cage. The dynamic fragility of fluids are highly particle shape dependent. It increases with particle dimensionality and falls with aspect ratio for quasi 1- and 2- dimentional particles. An ultralocal limit analysis of the NLE theory predicts universalities in the behavior of relaxation times, and elastic moduli. The equlibrium phase diagram of chemically anisotropic Janus spheres and Janus rods are calculated employing a mean field Random Phase Approximation. The calculations for Janus rods are corroborated by the full liquid state Reference Interaction Site Model theory. The Janus particles consist of attractive and repulsive regions. Both rods and spheres display rich phase behavior. The phase diagrams of these systems display fluid, macrophase separated, attraction driven microphase separated, repulsion driven microphase separated and crystalline regimes. Macrophase separation is predicted in highly attractive low volume fraction systems. Attraction driven microphase separation is charaterized by long length scale divergences, where the ordering length scale determines the microphase ordered structures. The ordering length scale of repulsion driven microphase separation is determined by the repulsive range. At the high volume fractions, particles forgo the enthalpic considerations of attractions and repulsions to satisfy hard core constraints and maximize vibrational entropy. This results in site length scale ordering in rods, and the sphere length scale ordering in Janus spheres, i.e., crystallization. A change in the Janus balance of both rods and spheres results in quantitative changes in spinodal temperatures and the position of phase boundaries. However, a change in the block sequence of Janus rods causes qualitative changes in the type of microphase ordered state, and induces prominent features (such as the Lifshitz point) in the phase diagrams of these systems. A detailed study of the number of nearest neighbors in Janus rod systems reflect a deep connection between this local measure of structure, and the structure factor which represents the most global measure of order.

Collimation of deuterium / 3-helium fusion products for advanced spacecraft propulsion and power

Current space exploration has transpired through the use of chemical rockets, and they have served us well, but they have their limitations. Exploration of the outer solar system, Jupiter and beyond will most likely require a new generation of propulsion system. One potential technology class to provide spacecraft propulsion and power systems involve thermonuclear fusion plasma systems. In this class it is well accepted that d-He3 fusion is the most promising of the fuel candidates for spacecraft applications as the 14.7 MeV protons carry up to 80% of the total fusion power while ‘s have energies less than 4 MeV. The other minor fusion products from secondary d-d reactions consisting of 3He, n, p, and 3H also have energies less than 4 MeV. Furthermore there are two main fusion subsets namely, Magnetic Confinement Fusion devices and Inertial Electrostatic Confinement (or IEC) Fusion devices. Magnetic Confinement Fusion devices are characterized by complex geometries and prohibitive structural mass compromising spacecraft use at this stage of exploration. While generating energy from a lightweight and reliable fusion source is important, another critical issue is harnessing this energy into usable power and/or propulsion. IEC fusion is a method of fusion plasma confinement that uses a series of biased electrodes that accelerate a uniform spherical beam of ions into a hollow cathode typically comprised of a gridded structure with high transparency. The inertia of the imploding ion beam compresses the ions at the center of the cathode increasing the density to the point where fusion occurs. Since the velocity distributions of fusion particles in an IEC are essentially isotropic and carry no net momentum, a means of redirecting the velocity of the particles is necessary to efficiently extract energy and provide power or create thrust. There are classes of advanced fuel fusion reactions where direct-energy conversion based on electrostatically-biased collector plates is impossible due to potential limits, material structure limitations, and IEC geometry. Thermal conversion systems are also inefficient for this application. A method of converting the isotropic IEC into a collimated flow of fusion products solves these issues and allows direct energy conversion. An efficient traveling wave direct energy converter has been proposed and studied by Momota , Shu and further studied by evaluated with numerical simulations by Ishikawa and others. One of the conventional methods of collimating charged particles is to surround the particle source with an applied magnetic channel. Charged particles are trapped and move along the lines of flux. By introducing expanding lines of force gradually along the magnetic channel, the velocity component perpendicular to the lines of force is transferred to the parallel one. However, efficient operation of the IEC requires a null magnetic field at the core of the device. In order to achieve this, Momota and Miley have proposed a pair of magnetic coils anti-parallel to the magnetic channel creating a null hexapole magnetic field region necessary for the IEC fusion core. Numerically, collimation of 300 eV electrons without a stabilization coil was demonstrated to approach 95% at a profile corresponding to Vsolenoid = 20.0V, Ifloating = 2.78A, Isolenoid = 4.05A while collimation of electrons with stabilization coil present was demonstrated to reach 69% at a profile corresponding to Vsolenoid = 7.0V, Istab = 1.1A, Ifloating = 1.1A, Isolenoid = 1.45A. Experimentally, collimation of electrons with stabilization coil present was demonstrated experimentally to be 35% at 100 eV and reach a peak of 39.6% at 50eV with a profile corresponding to Vsolenoid = 7.0V, Istab = 1.1A, Ifloating = 1.1A, Isolenoid = 1.45A and collimation of 300 eV electrons without a stabilization coil was demonstrated to approach 49% at a profile corresponding to Vsolenoid = 20.0V, Ifloating = 2.78A, Isolenoid = 4.05A 6.4% of the 300eV electrons’ initial velocity is directed to the collector plates. The remaining electrons are trapped by the collimator’s magnetic field. These particles oscillate around the null field region several hundred times and eventually escape to the collector plates. At a solenoid voltage profile of 7 Volts, 100 eV electrons are collimated with wall and perpendicular component losses of 31%. Increasing the electron energy beyond 100 eV increases the wall losses by 25% at 300 eV. Ultimately it was determined that a field strength deriving from 9.5 MAT/m would be required to collimate 14.7 MeV fusion protons from d-3He fueled IEC fusion core. The concept of the proton collimator has been proven to be effective to transform an isotropic source into a collimated flow of particles ripe for direct energy conversion.