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.

Design and development of distributed feedback transistor lasers

The transistor laser is a unique three-port device that operates simultaneously as a transistor and a laser. With quantum wells incorporated in the base regions of heterojunction bipolar transistors, the transistor laser possesses advantageous characteristics of fast base spontaneous carrier lifetime, high differential optical gain, and electrical-optical characteristics for direct “read-out” of its optical properties. These devices have demonstrated many useful features such as high-speed optical transmission without the limitations of resonance, non-linear mixing, frequency multiplication, negative resistance, and photon-assisted switching. To date, all of these devices operate as multi-mode lasers without any type of wavelength selection or stabilizing mechanisms. Stable single-mode distributed feedback diode laser sources are important in many applications including spectroscopy, as pump sources for amplifiers and solid-state lasers, for use in coherent communication systems, and now as TLs potentially for integrated optoelectronics. The subject of this work is to expand the future applications of the transistor laser by demonstrating the theoretical background, process development and device design necessary to achieve singlelongitudinal- mode operation in a three-port transistor laser. A third-order distributed feedback surface grating is fabricated in the top emitter AlGaAs confining layers using soft photocurable nanoimprint lithography. The device produces continuous wave laser operation with a peak wavelength of 959.75 nm and threshold current of 13 mA operating at -70 °C. For devices with cleaved ends a side-mode suppression ratio greater than 25 dB has been achieved.

Low-power high-performance SAR ADC design with digital calibration techniques

This dissertation presents the design of three high-performance successive-approximation-register (SAR) analog-to-digital converters (ADCs) using distinct digital background calibration techniques under the framework of a generalized code-domain linear equalizer. These digital calibration techniques effectively and efficiently remove the static mismatch errors in the analog-to-digital (A/D) conversion. They enable aggressive scaling of the capacitive digital-to-analog converter (DAC), which also serves as sampling capacitor, to the kT/C limit. As a result, outstanding conversion linearity, high signal-to-noise ratio (SNR), high conversion speed, robustness, superb energy efficiency, and minimal chip-area are accomplished simultaneously. The first design is a 12-bit 22.5/45-MS/s SAR ADC in 0.13-μm CMOS process. It employs a perturbation-based calibration based on the superposition property of linear systems to digitally correct the capacitor mismatch error in the weighted DAC. With 3.0-mW power dissipation at a 1.2-V power supply and a 22.5-MS/s sample rate, it achieves a 71.1-dB signal-to-noise-plus-distortion ratio (SNDR), and a 94.6-dB spurious free dynamic range (SFDR). At Nyquist frequency, the conversion figure of merit (FoM) is 50.8 fJ/conversion step, the best FoM up to date (2010) for 12-bit ADCs. The SAR ADC core occupies 0.06 mm2, while the estimated area the calibration circuits is 0.03 mm2. The second proposed digital calibration technique is a bit-wise-correlation-based digital calibration. It utilizes the statistical independence of an injected pseudo-random signal and the input signal to correct the DAC mismatch in SAR ADCs. This idea is experimentally verified in a 12-bit 37-MS/s SAR ADC fabricated in 65-nm CMOS implemented by Pingli Huang. This prototype chip achieves a 70.23-dB peak SNDR and an 81.02-dB peak SFDR, while occupying 0.12-mm2 silicon area and dissipating 9.14 mW from a 1.2-V supply with the synthesized digital calibration circuits included. The third work is an 8-bit, 600-MS/s, 10-way time-interleaved SAR ADC array fabricated in 0.13-μm CMOS process. This work employs an adaptive digital equalization approach to calibrate both intra-channel nonlinearities and inter-channel mismatch errors. The prototype chip achieves 47.4-dB SNDR, 63.6-dB SFDR, less than 0.30-LSB differential nonlinearity (DNL), and less than 0.23-LSB integral nonlinearity (INL). The ADC array occupies an active area of 1.35 mm2 and dissipates 30.3 mW, including synthesized digital calibration circuits and an on-chip dual-loop delay-locked loop (DLL) for clock generation and synchronization.

Applications of functional nucleic acids in imaging, sensing and drug delivery and investigations of DNAzyme-metal interactions

Functional nucleic acids (FNA), including nucleic acids catalysts (ribozymes and DNAzymes) and ligands (aptamers), have been discovered in nature or isolated in a laboratory through a process called in vitro selection. They are nucleic acids with functions similar to protein enzymes or antibodies. They have been developed into sensors with high sensitivity and selectivity; it is realized by converting the reaction catalyzed by a DNAzyme/ribozyme or the binding event of an aptamer to a fluorescent, colorimetric or electrochemical signal. While a number of studies have been reported for in vitro sensing using DNAzymes or aptamers, there are few reports on in vivo sensing or imaging. MRI is a non-invasive imaging technique; smart MRI contrast agents were synthesized for molecular imaging purposes. However, their rational design remains a challenge due to the difficulty to predict molecular interactions. Chapter 2 focuses on rational design of smart T1-weighted MRI contrast agents with high specificity based on DNAzymes and aptamers. It was realized by changing the molecular weight of the gadolinium conjugated DNA strand with the analytes, which lead to analyte-specific water proton relaxation responses and contrast changes on an MRI image. The designs are general; the high selectivity of FNA was retained. Most FNA-based fluorescent sensors require covalent labeling of fluorophore/quencher to FNAs, which incurrs extra expenses and could interfere the function of FNAs. Chapter 3 describes a new sensor design avoiding the covalent labeling of fluorophore and quencher. The fluorescence of malachite green (MG) was regulated by the presence of adenosine. Conjugate of aptamers of MG and adenosine and a bridge strand were annealed in a solution containing MG. The MG aptamer did not bind MG because of its hybridization to the bridge strand, resulting in low fluorescence signal of MG. The hybridization was weakened in the presence of adenosine, leading to the binding of MG to its aptamer and a fluorescence increase. The sensor has comparable detection limit (20 micromolar) and specificity to its labeled derivatives. Enzymatic activity of most DNAzymes requires metal cations. The research on the metal-DNAzyme interaction is of interest and challenge to scientists because of the lack of structural information. Chapters 4 presents the research on the characterization of the interaction between a Cu2+-dependent DNAzyme and Cu2+. Electron paramagnetic resonance (EPR) and UV-Vis spectroscopy were used to probe the binding of Cu2+ to the DNAzyme; circular dichroism was used to probe the conformational change of the DNAzyme induced by Cu2+. It was proposed that the conformational change by the Cu2+ binding is important for the activity of the DNAzyme. Chapter 5 reports the dependence of the activity of 8-17 DNAzyme on the presence of both Pb2+ and other metal cations including Zn2+, Cd2+ and Mg2+. It was discovered that presence of those metal cations can be cooperative or inhibitive to 8-17 activity. It is hypothesized that the 8-17 DNAzyme had multiple binding sites for metal cations based on the results. Cisplatin is effective killing tumor cells, but with significant side effects, which can be minimized by its targeted delivery. Chapter 6 focuses on the effort to functionalize liposomes encapsulating cisplatin by an aptamer that selectively bind nucleolin, an overexpressed protein by breast cancer cells. The study proved the selective cytotoxicity to breast cancer cells of the aptamer-functionalized liposome.