This thesis involves the study of a range of geometric covering and piercing problems, where the unifying thread is approximation using disks. While some of the problems addressed in this work are solved exactly with polynomial time algorithms, many problems are shown to be at least NP-hard. For the latter, approximation algorithms are the best that we can do in polynomial time assuming that P is not equal to NP. One of the best known problems involving unit disks is the Discrete Unit Disk Cover (DUDC) problem, in which the input consists of a set of points P and a set of unit disks in the plane D, and the objective is to compute a subset of the disks of minimum cardinality which covers all of the points. Another perspective on the problem is to consider the centre points (denoted Q) of the disks D as an approximating set of points for P. An optimal solution to DUDC provides a minimal cardinality subset Q*, a subset of Q, so that each point in P is within unit distance of a point in Q*. In order to approximate the general DUDC problem, we also examine several restricted variants. In the Line-Separable Discrete Unit Disk Cover (LSDUDC) problem, P and Q are separated by a line in the plane. We write that l^- is the half-plane defined by l containing P, and l^+ is the half-plane containing Q. LSDUDC may be solved exactly in O(m^2n) time using a greedy algorithm. We augment this result by describing a 2-approximate solution for the Assisted LSDUDC problem, where the union of all disks centred in l^+ covers all points in P, but we consider using disks centred in l^- as well to try to improve the solution. Next, we describe the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, where P and Q are confined to a strip of the plane of height h. We show that this problem is NP-complete, and we provide a range of approximation algorithms for the problem with trade-offs between the approximation factor and running time. We outline approximation algorithms for the general DUDC problem which make use of the algorithms for LSDUDC and WSDUDC. These results provide the fastest known approximation algorithms for DUDC. As with the WSDUDC results, we present a set of algorithms in which better approximation factors may be had at the expense of greater running time, ranging from a 15-approximate algorithm which runs in O(mn + m log m + n log n) time to a 18-approximate algorithm which runs in O(m^6n+n log n) time. The next problems that we study are Hausdorff Core problems. These problems accept an input polygon P, and we seek a convex polygon Q which is fully contained in P and minimizes the Hausdorff distance between P and Q. Interestingly, we show that this problem may be reduced to that of computing the minimum radius of disk, call it k_opt, so that a convex polygon Q contained in P intersects all disks of radius k_opt centred on the vertices of P. We begin by describing a polynomial time algorithm for the simple case where P has only a single reflex vertex. On general polygons, we provide a parameterized algorithm which performs a parametric search on the possible values of k_opt. The solution to the decision version of the problem, i.e. determining whether there exists a Hausdorff Core for P given k_opt, requires some novel insights. We also describe an FPTAS for the decision version of the Hausdorff Core problem. Finally, we study Generalized Minimum Spanning Tree (GMST) problems, where the input consists of imprecise vertices, and the objective is to select a single point from each imprecise vertex in order to optimize the weight of the MST over the points. In keeping with one of the themes of the thesis, we begin by using disks as the imprecise vertices. We show that the minimization and maximization versions of this problem are NP-hard, and we describe some parameterized and approximation algorithms. Finally, we look at the case where the imprecise vertices consist of just two vertices each, and we show that the minimization version of the problem (which we call 2-GMST) remains NP-hard, even in the plane. We also provide an algorithm to solve the 2-GMST problem exactly if the combinatorial structure of the optimal solution is known. We identify a number of open problems in this thesis that are worthy of further study. Among them: Is the Assisted LSDUDC problem NP-complete? Can the WSDUDC results be used to obtain an improved PTAS for DUDC? Are there classes of polygons for which the determination of the Hausdorff Core is easy? Is there a PTAS for the maximum weight GMST problem on (unit) disks? Is there a combinatorial approximation algorithm for the 2-GMST problem (particularly with an approximation factor under 4)?

An investigation of the problem of inelastic scattering process under the Coulomb Born approximation is given. Different approaches to calculate Coulomb wavefunctions in the momentum space representation are analyzed and a discussion of their existences in the generalized distribution sense is provided. Inokuti’s approach of finding the differential cross section in the momentum space representation under the Coulomb Born approximation is described and a different approach with an application of the Bremsstrahlung integral is developed and compared with Inokuti’s approach.

Paper is a complex fibrous material whose production involves substantial amounts of natural and industrial resources. To reduce its manufacturing costs, the pulp and paper industry often employs optical technology such as high sensitivity laser sensors used to measure physical parameters like thickness and opacity. More recently, computer simulations of paper optical properties are also being used to accelerate the research cycle required to the development of new types of paper. In these simulations, the bulk scattering of paper is usually approximated by analytical formulas, notably the Henyey-Greenstein function. In this work, we qualitatively investigate the degree of accuracy of such approximations with respect to collimated light. More specifically, an experimental set-up was devised to record the transmission of red and green HeNe lasers through different paper samples. The measured data was compared with data obtained using the Henyey-Greenstein function and data obtained using an alternative exponentiated cosine function. The comparisons are used to qualitatively assess the degree of accuracy of the bulk scattering approximations provided by both functions. This work closes with a discussion on the practical implications of our findings for the modeling of paper optical properties.

A Markov Decision Process (MDP) is a model employed to describe problems in which a decision must be made at each one of several stages, while receiving feedback from the environment. This type of model has been extensively studied in the operations research community and fundamental algorithms have been developed to solve associated problems. However, these algorithms are quite inefficient for very large problems, leading to a need for alternatives; since MDP problems are provably hard on compressed representations, one becomes content even with algorithms which may perform well at least on specific classes of problems. The class of problems we deal with in this thesis allows succinct representations for the MDP as a dynamic Bayes network, and for its solution as a weighted combination of basis functions. We develop novel algorithms for producing, improving, and calculating the error of approximate solutions for MDPs using a compressed representation. Specifically, we develop an efficient branch-and-bound algorithm for computing the Bellman error of the compact approximate solution regardless of its provenance. We introduce an efficient direct linear programming algorithm which, using incremental constraints generation, achieves run times significantly smaller than existing approximate algorithms without much loss of accuracy. We also show a novel direct linear programming algorithm which, instead of employing constraints generation, transforms the exponentially many constraints into a compact form more amenable for tractable solutions. In spite of its perceived importance, the efficient optimization of the Bellman error towards an approximate MDP solution has eluded current algorithms; to this end we propose a novel branch-and-bound approximate policy iteration algorithm which makes direct use of our branch-and-bound method for computing the Bellman error. We further investigate another procedure for obtaining an approximate solution based on the dual of the direct, approximate linear programming formulation for solving MDPs. To address both the loss of accuracy resulting from the direct, approximate linear program solution and the question of where basis functions come from we also develop a principled system able not only to produce the initial set of basis functions, but also able to augment it with new basis functions automatically generated such that the approximation error decreases according to the user's requirements and time limitations.

An investigation of the problem of inelastic scattering process under the Coulomb Born approximation is given. Different approaches to calculate Coulomb wavefunctions in the momentum space representation are analyzed and a discussion of their existences in the generalized distribution sense is provided. Inokuti’s approach of finding the differential cross section in the momentum space representation under the Coulomb Born approximation is described and a different approach with an application of the Bremsstrahlung integral is developed and compared with Inokuti’s approach.

Paper is a complex fibrous material whose production involves substantial amounts of natural and industrial resources. To reduce its manufacturing costs, the pulp and paper industry often employs optical technology such as high sensitivity laser sensors used to measure physical parameters like thickness and opacity. More recently, computer simulations of paper optical properties are also being used to accelerate the research cycle required to the development of new types of paper. In these simulations, the bulk scattering of paper is usually approximated by analytical formulas, notably the Henyey-Greenstein function. In this work, we qualitatively investigate the degree of accuracy of such approximations with respect to collimated light. More specifically, an experimental set-up was devised to record the transmission of red and green HeNe lasers through different paper samples. The measured data was compared with data obtained using the Henyey-Greenstein function and data obtained using an alternative exponentiated cosine function. The comparisons are used to qualitatively assess the degree of accuracy of the bulk scattering approximations provided by both functions. This work closes with a discussion on the practical implications of our findings for the modeling of paper optical properties.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

This thesis studies three topics in quantum computation and information: The approximability of quantum problems, quantum proof systems, and non-classical correlations in quantum systems. Our first area of study concerns the approximability of computational problems which are complete for quantum complexity classes. In the classical setting, the study of approximation algorithms and hardness of approximation is one of the main research areas of theoretical computer science. Yet, little is known regarding approximability in the quantum setting. We first demonstrate a polynomial-time approximation algorithm for dense instances of the canonical QMA-complete quantum constraint satisfaction problem, the local Hamiltonian problem. We next go in the opposite direction by first introducing a quantum generalization of the polynomial-time hierarchy. We then introduce problems which are not only complete for the second level of this hierarchy, but are in fact hard to approximate. Our second area of study concerns quantum proof systems. Here, an interesting question which remains open despite much effort is whether a proof system with multiple unentangled quantum provers is equal in expressive power to a proof system with a single quantum prover (i.e. is QMA(poly) equal to QMA?). Our results here study variants of this question, and include a proof that the class BellQMA(poly) collapses to QMA. We also give an alternate proof that SepQMA(m) admits perfect parallel repetition. This proof is novel in that it utilizes cone programming duality. Our final area of study concerns non-classical correlations in quantum systems. Specifically, there exist genuinely quantum correlations beyond entanglement in mixed quantum states which may prove useful from a computing and information theoretic perspective. We first explore the presence of such correlations in the locking of classical correlations and the DQC1 model of mixed-state quantum computing. Our second result introduces a novel scheme for quantifying non-classical correlations using local unitary operations. Our third result introduces a protocol through which non-classical correlations in a starting system can be “activated”' into distillable entanglement with an ancilla system. Our last result determines when the entanglement generated in the activation protocol above can be mapped back onto the starting state via entanglement swapping.

Input¬output approximation of spacecraft motion is convenient and necessary in many situations. For a rigid¬body spacecraft, this process is simple because the system is governed by a set of equations that is linear in the system parameters. However, the combination of a flexible appendage and a rigid hub adds complexity by increasing the degrees of freedom and by introducing nonlinear coupling between the hub and appendage. Assumed Modes is one technique for modeling flexible body motion. Traditional Assumed Modes uses a set of linear assumed modes, but when dealing with rotating flexible systems, a modification of this method allows for the use of quadratic assumed modes. The quadratic assumed model provides an increased level of sophistication, but the derivation still neglects a set of higher¬order terms. This work develops the nonlinear equations of motion that arise from retaining these nonlinear, higher¬order terms. Simulation results reveal that the inclusion of these terms noticeably changes the motion of the system. Once the equations of motion have been developed, focus turns to the input¬output mapping of a system that is simulated using this set of equations. Approxi¬mating linear systems is straightforward, and many methods exist that can success¬fully perform this function. On the other hand, few approximation methods exist for nonlinear systems. Researchers at Texas A&M University recently developed one such method that obtains a linear estimation and then uses an adaptive polynomial estimation method to compensate for the disparity between that estimate and the true measurements. This research includes an in¬depth investigation of this nonlinear approximation technique. Finally, these two major research thrusts are combined, and input¬output approx¬imation is performed on the nonlinear rotational spacecraft model developed herein. The results of this simulation show that the nonlinear method holds a significant advantage over a traditional linear method in certain situations. Specifically, the nonlinear algorithm provides superior approximation for systems with nonzero natu¬ral frequencies. For the algorithm to be successful when rigid¬body modes are present, the system motion must be persistently exciting. This research is an important first step toward developing a nonlinear parameter identification algorithm.

The main idea of this paper is inspired by a paper written together by my advisor Dr. Hang, Dr. Huang of the Industrial Technology Research Institute, and Dr. Chao of Institute of Applied Mechanics of National Taiwan University[quant-ph/0506153 v1,2005]. After some mathematical calculations we can extend the WKB approximation to treat position-dependent effective mass problem (PDEM). Then we did simulation on a model PDEM problem to compare the well-know closed form solution and the extended WKB approximation. We demonstrated that the extended WKB approximation not only can obtain the eigenvalues very accurately, but also is very useful to estimate the distribution of the wave function. We also found the modulation on the oscillations of wave function under PDEM by the extended WKB approximation.