Browsing Combinatorics and Optimization by Issue Date
Now showing items 41-60 of 436
-
Hyperpfaffians in Algebraic Combinatorics
(University of Waterloo, 2006)The pfaffian is a classical tool which can be regarded as a generalization of the determinant. The hyperpfaffian, which was introduced by Barvinok, generalizes the pfaffian to higher dimension. This was further ... -
On the Crossing Numbers of Complete Graphs
(University of Waterloo, 2006)In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K<sub>n</sub></em> must be a triangle (for <em>n</em> ≥ 3). We prove that, ... -
The Cycle Spaces of an Infinite Graph
(University of Waterloo, 2006)The edge space of a finite graph <em>G</em> = (<em>V</em>, <em>E</em>) over a field F is simply an assignment of field elements to the edges of the graph. The edge space can equally be thought of us an |<em>E</em>|-dimensional ... -
Algebraic Analysis of Vertex-Distinguishing Edge-Colorings
(University of Waterloo, 2006)Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively ... -
Portfolio Selection Under Nonsmooth Convex Transaction Costs
(University of Waterloo, 2006)We consider a portfolio selection problem in the presence of transaction costs. Transaction costs on each asset are assumed to be a convex function of the amount sold or bought. This function can be nondifferentiable ... -
Numerical Stability in Linear Programming and Semidefinite Programming
(University of Waterloo, 2006)We study numerical stability for interior-point methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. ... -
On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs
(University of Waterloo, 2006)The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all ... -
Approximate Private Quantum Channels
(University of Waterloo, 2006)This thesis includes a survey of the results known for private and approximate private quantum channels. We develop the best known upper bound for ε-randomizing maps, <em>n</em> + 2log(1/ε) + <em>c</em> ... -
Scarf's Theorem and Applications in Combinatorics
(University of Waterloo, 2006-12-19)A theorem due to Scarf in 1967 is examined in detail. Several versions of this theorem exist, some which appear at first unrelated. Two versions can be shown to be equivalent to a result due to Sperner in 1928: for a ... -
Minimum Crossing Problems on Graphs
(University of Waterloo, 2007-01-19)This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in ... -
On Prime-Order Elliptic Curves with Embedding Degrees 3, 4 and 6
(University of Waterloo, 2007-01-22)Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are ... -
Probabilistic Choice Models for Product Pricing Using Reservation Prices
(University of Waterloo, 2007-01-22)The problem of pricing a product line to maximize profits is an important challenge faced by many companies. To address this problem, we discuss four different probabilistic choice models that are based on reservation ... -
On Excluded Minors for Even Cut Matroids
(University of Waterloo, 2007-01-22)In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph we can associate an even cut matroid. However, given an even cut matroid, there are ... -
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming
(University of Waterloo, 2007-05-18)Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound ... -
Applications of Semidefinite Programming in Quantum Cryptography
(University of Waterloo, 2007-05-18)Coin-flipping is the cryptographic task of generating a random coin-flip between two mistrustful parties. Kitaev discovered that the security of quantum coin-flipping protocols can be analyzed using semidefinite programming. ... -
MAC Constructions: Security Bounds and Distinguishing Attacks
(University of Waterloo, 2007-05-18)We provide a simple and improved security analysis of PMAC, a Parallelizable MAC (Message Authentication Code) defined over arbitrary messages. A similar kind of result was shown by Bellare, Pietrzak and Rogaway at ... -
Combinatorial Approaches To The Jacobian Conjecture
(University of Waterloo, 2007-08-24)The Jacobian Conjecture is a long-standing open problem in algebraic geometry. Though the problem is inherently algebraic, it crops up in fields throughout mathematics including perturbation theory, quantum field theory ... -
Dominating sets in Kneser graphs
(University of Waterloo, 2007-08-29)This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting ... -
Mathematical Programming Formulations of the Planar Facility Location Problem
(University of Waterloo, 2007-09-24)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 ... -
Algebraic Methods for Reducibility in Nowhere-Zero Flows
(University of Waterloo, 2007-09-25)We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of ...