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.

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)?

Small Unmanned Aerial Vehicles (UAVs) are currently used in several surveillance applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle can carry. In the thesis, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total length of the path is a minimum. Mixed integer, linear programming formulations are proposed to solve the problem optimally. As solving these formulations to optimality may take a large amount of time, fast and efficient construction and improvement heuristics are developed to find good sub-optimal solutions to the problem. Simulation results are also presented to corroborate the performance of all the algorithms. In addition to the above contributions, this thesis develops an approximation algorithm for a multiple UAV routing problem with fuel constraints.

Thesis (Ph.D.)--University of Melbourne, Dept. of Mathematics and Statistics, 2001. / Typescript (photocopy). Includes bibliographical references (leaves 126-128).

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008. / Includes bibliographical references (leaves 88-98). Also available in electronic version.

Zugl.: Kaiserslautern, Techn. Univ., Diss., 2008

Thesis (M.S. in Physics)--Naval Postgraduate School, December 2008. / Thesis Advisor(s): Borden, Brett. "December 2008." Description based on title screen as viewed on January 29, 2009. Includes bibliographical references (p. 83-84). Also available in print.

Thesis (M.S.)--Virginia Polytechnic Institute and State University, 1994. / Vita. Abstract. Includes bibliographical references (leaves 41-42). Also available via the Internet.

Thesis (Ph. D.)--Rutgers University, 2010. / "Graduate Program in Statistics and Biostatistics." Includes bibliographical references (p. 55-57).