The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then present algebraic characterizations of these valid inequalities. Tightly based on our algebraic characterizations, we give an alternate proof of a result of Lovasz and Schrijver, establishing the equivalence of N and N_0 operators on the fractional stable set polytope. Since the above mentioned conjectures involve also the recursive applications of N and N_0 operators, we also study the valid inequalities obtained by these lift-and-project operators after two applications. We show that the N-N_0 Conjecture is false, while the Rank Conjecture is true for all graphs with no more than 8 nodes.

Rayleigh matroids are a class of matroids with sets of bases that satisfy a strong negative correlation property. Interesting characteristics include the existence of an efficient algorithm for sampling the bases of a Rayleigh matroid [7]. It has been conjectured that the class of Rayleigh matroids satisfies Mason’s conjecture [14]. Though many elementary properties of Rayleigh matroids have been established, it is not known if this class has a finite set of minimal excluded minors. At this time, it seems unlikely that this is the case. It has been shown that there is a single minimal excluded minor for the smaller class of binary Rayleigh matroids [5]. The aim of this thesis is to detail our search for the set of minimal excluded minors for ternary Rayleigh matroids. We have found several minimal excluded minors for the above class of matroids. However, our search is incomplete. It is unclear whether the set of excluded minors for this set of matroids is finite or not, and, if finite, what the complete set of minimal excluded minors is. For our method to answer this question definitively will require a new computer program. This program would automate a step in our process that we have done by hand: writing polynomials in at least ten indeterminates as a sum with many terms, squared.

This thesis is devoted to the analysis of a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with large girth. This class is useful because, by conveniently setting the parameters associated with it, we may derive algorithms for some well-known graph problems, such as algorithms to find a large independent set, a large induced forest, or even a small dominating set in an input graph G. The name ``locally greedy" comes from the fact that, in an algorithm of this class, the probability associated with the random selection of a vertex v is determined by the current state of the vertices within some fixed distance of v. Given r > 2 and an r-regular graph G, we determine the expected performance of a locally greedy algorithm in G, depending on the girth g of the input and on the degree r of its vertices. When the girth of the graph is sufficiently large, this analysis leads to new lower bounds on the independence number of G and on the maximum number of vertices in an induced forest in G, which, in both cases, improve the bounds previously known. It also implies bounds on the same functions in graphs with large girth and maximum degree r and in random regular graphs. As a matter of fact, the asymptotic lower bounds on the cardinality of a maximum induced forest in a random regular graph improve earlier bounds, while, for independent sets, our bounds coincide with asymptotic lower bounds first obtained by Wormald. Our result provides an alternative proof of these bounds which avoids sharp concentration arguments. The main contribution of this work lies in the method presented rather than in these particular new bounds. This method allows us, in some sense, to directly analyse prioritised algorithms in regular graphs, so that the class of locally greedy algorithms, or slight modifications thereof, may be applied to a wider range of problems in regular graphs with large girth.

This thesis focuses on convex sets and convex cones defined using hyperbolic polynomials. We first review some of the theory of convex sets in $\R^d$ in general. We then review some classical algebraic theorems concerning polynomials in a single variable, as well as presenting a few more modern results about them. We then discuss the theory of hyperbolic polynomials in several variables and their associated hyperbolicity cones. We survey various ways to build and decompose hyperbolic cones and we prove that every nontrivial hyperbolic cone is the intersection of its derivative cones. We conclude with a brief discussion of the set of extreme rays of a hyperbolic cone.

The thesis describes new results for several problems in random graph theory. The first problem relates to the uniform random graph model in the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices and $M=n/2+s$ edges for $s=s(n)$ satisfying $n^{2/3}=o(s)$ and $s=o(n)$. The property studied is the length of the longest cycle in the graph. We give a new upper bound, which holds asymptotically almost surely, on this length. As part of our proof we establish a result about the heaviest cycle in a certain randomly-edge-weighted nearly-3-regular graph, which may be of independent interest. Our second result is a new contiguity result for a random $d$-regular graph. Let $j=j(n)$ be a function that is linear in $n$. A $(d,d-1)$-irregular graph is a graph which is $d$-regular except for $2j$ vertices of degree $d-1$. A $j$-edge matching in a graph is a set of $j$ independent edges. In this thesis we prove the new result that a random $(d,d-1)$-irregular graph plus a random $j$-edge matching is contiguous to a random $d$-regular graph, in the sense that in the two spaces, the same events have probability approaching 1 as $n\to\infty$. This allows one to deduce properties, such as colourability, of the random irregular graph from the corresponding properties of the random regular one. The proof applies the small subgraph conditioning method to the number of $j$-edge matchings in a random $d$-regular graph. The third problem is about the 3-colourability of a random 5-regular graph. Call a colouring balanced if the number of vertices of each colour is equal, and locally rainbow if every vertex is adjacent to vertices of all the other colours. Using the small subgraph conditioning method, we give a condition on the variance of the number of locally rainbow balanced 3-colourings which, if satisfied, establishes that the chromatic number of the random 5-regular graph is asymptotically almost surely equal to 3. We also describe related work which provides evidence that the condition is likely to be true. The fourth problem is about the chromatic number of a random $d$-regular graph for fixed $d$. Achlioptas and Moore recently announced a proof that a random $d$-regular graph asymptotically almost surely has chromatic number $k-1$, $k$, or $k+1$, where $k$ is the smallest integer satisfying $d < 2(k-1)\log(k-1)$. In this thesis we prove that, asymptotically almost surely, it is not $k+1$, provided a certain second moment condition holds. The proof applies the small subgraph conditioning method to the number of balanced $k$-colourings, where a colouring is balanced if the number of vertices of each colour is equal. We also give evidence that suggests that the required second moment condition is true.

It is known that almost all 2-qubit gates are universal for quantum computing (Lloyd 1995; Deutsch, Barenco, Eckert 1995). However, an explicit characterization of non-universal 2-qubit gates is not known. We consider a closely related problem of characterizing the set of non-universal 2-qubit Hamiltonians. We call a 2-qubit Hamiltonian n-universal if, when applied on different pairs of qubits, it can be used to approximate any unitary operation on n qubits. It follows directly from the results of Lloyd and Deutsch, Barenco, Eckert, that almost any 2-qubit Hamiltonian is 2-universal. Our main result is a complete characterization of 2-non-universal 2-qubit Hamiltonians. There are three cases when a 2-qubit Hamiltonian H is not universal: (1) H shares an eigenvector with the gate that swaps two qubits; (2) H acts on the two qubits independently (in any of a certain family of bases); (3) H has zero trace. The last condition rules out the Hamiltonians that generate SU(4)---it can be omitted if the global phase is not important. A Hamiltonian that is not 2-universal can still be 3-universal. We give a (possibly incomplete) list of 2-qubit Hamiltonians that are not 3-universal. If this list happens to be complete, it actually gives a classification of n-universal 2-qubit Hamiltonians for all n >= 3.

Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular intervals. In this thesis, we model these two problems and develop algorithms to solve them. In doing so, we encounter many theoretical problems that are both applicable to Zip’s operations and intrinsically interesting problems independent of the application. First, we note that the assignment problem facing Zip is inherently in an online setting. With returns of DVDs being processed throughout the day, the dataset is constantly changing. Although the ideal solution would be to wait until the end of the day to make decisions, physical work load capacities prevent this. For this reason we discuss two online problems, online 0-1 budgeted matching and the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids and cost get small compared to the budgets, where S is the ratio of the highest and lowest ratios of bids to costs. We suggest a linear programming approach to solve Zip’s assignment problem. We develop an integer program that models the B-matching instance with additional constraints of concern to Zip, and prove that this integer program belongs to a larger class of integer programs that has totally unimodular constraint matrices. Thus, the assignment problem can be solved to optimality every thirty minutes. We additionally create a test environment to check daily performance, and provide real-time implementation results, showing a marked improvement over Zip’s old algorithm. We show that Zip’s purchasing problem can be modeled by the matching augmentation problem defined as follows. Given a graph with vertex capacities and costs, edge weights, and budget C, find a purchasing of additional node capacity of cost at most C that admits a B-matching of maximum weight. We give a PTAS for this problem, and then present a special case that is polynomial time solvable that still models Zip’s purchasing problem, under the assumption of uniform costs. We then extend the augmentation idea to matroids and present matroid augmentation, matroid knapsack, and matroid intersection knapsack, three NP-hard problems. We give an FPTAS for matroid knapsack by dynamic programming, PTASes for the other two, and demonstrate applications of these problems.

The study of the infinite (countable) family of partial differential equations known as the Kadomtzev - Petviashvili (KP) hierarchy has received much interest in the mathematical and theoretical physics community for over forty years. Recently there has been a renewed interest in its application to enumerative combinatorics inspired by Witten's conjecture (now Kontsevich's theorem). In this thesis we provide a detailed development of the KP hierarchy and some of its applications with an emphasis on the combinatorics involved. Up until now, most of the material pertaining to the KP hierarchy has been fragmented throughout the physics literature and any complete accounts have been for purposes much diff erent than ours. We begin by describing a family of related Lie algebras along with a module on which they act. We then construct a realization of this module in terms of polynomials and determine the corresponding Lie algebra actions. By doing this we are able to describe one of the Lie group orbits as a family of polynomials and the equations that de fine them as a family of partial diff erential equations. This then becomes the KP hierarchy and its solutions. We then interpret the KP hierarchy as a pair of operators on the ring of symmetric functions and describe their action combinatorially. We then conclude the thesis with some combinatorial applications.

We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large random regular graphs beginning with small ones. We prove that the limiting joint distribution of the numbers of short cycles in the resulting graph is independent Poisson. We use the coupling method to bound the total variation distance between the joint distribution of short cycle counts and its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound of the $\eps$-mixing time. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. We also show that the $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound is essentially tight. We study also the connectivity of random $d$-regular graphs generated by the pegging algorithm. We show that these graphs are asymptotically almost surely $d$-connected for any even constant $d\ge 4$. The problem of orientation of random hypergraphs is motivated by the classical load balancing problem. Let $h>w>0$ be two fixed integers. Let $\orH$ be a hypergraph whose hyperedges are uniformly of size $h$. To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to this hyperedge, and the rest negative. A $(w,k)$-orientation of $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The other topic we discuss is computing the probability of induced subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is $H$. The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of random graphs with given degree sequence $\bf d$. This result provides a basic tool for studying properties, for instance the existence or the counts, of certain types of induced subgraphs.