Browsing Combinatorics and Optimization by Title
Now showing items 352-371 of 436
-
Quantum Walks on Strongly Regular Graphs
(University of Waterloo, 2010-08-30)This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the ... -
A Quick-and-Dirty Approach to Robustness in Linear Optimization
(University of Waterloo, 2013-01-07)We introduce methods for dealing with linear programming (LP) problems with uncertain data, using the notion of weighted analytic centers. Our methods are based on high interaction with the decision maker (DM) and try ... -
Ramsey-nice families of graphs
(Elsevier, 2018-08)For a finite family $\cF$ of fixed graphs let $R_k(\cF)$ be the smallest integer $n$ for which every $k$-coloring of the edges of the complete graph $K_n$ yields a monochromatic copy of some $F\in\cF$. We say that $\cF$ ... -
Rayleigh Property of Lattice Path Matroids
(University of Waterloo, 2015-09-22)In this work, we studied the class of lattice path matroids $\mathcal{L}$, which was first introduced by J.E. Bonin. A.D. Mier, and M. Noy in [\ref{Bonin 2002}]. Lattice path matroids are transversal, and $\mathcal{L}$ is ... -
Real equiangular lines and related codes
(University of Waterloo, 2020-01-24)We consider real equiangular lines and related codes. The driving question is to find the maximum number of equiangular lines in a given dimension. In the real case, this is controlled by combinatorial phenomena, and until ... -
Recognizing Even-Cycle and Even-Cut Matroids
(University of Waterloo, 2016-04-27)Even-cycle and even-cut matroids are classes of binary matroids that generalize respectively graphic and cographic matroids. We give algorithms to check membership for these classes of matroids. We assume that the matroids ... -
Recovery Guarantees for Graph Clustering Problems
(University of Waterloo, 2021-12-06)Graph clustering is widely-studied unsupervised learning problem in which the task is to group similar entities together based on observed pairwise entity interactions. This problem has applications in diverse domains such ... -
Regularization Using a Parameterized Trust Region Subproblem
(University of Waterloo, 2004)We present a new method for regularization of ill-conditioned problems that extends the traditional trust-region approach. Ill-conditioned problems arise, for example, in image restoration or mathematical processing of ... -
Relaxations of the Maximum Flow Minimum Cut Property for Ideal Clutters
(University of Waterloo, 2021-01-29)Given a family of sets, a covering problem consists of finding a minimum cost collection of elements that hits every set. This objective can always be bound by the maximum number of disjoint sets in the family, we refer ... -
Representations of even-cycle and even-cut matroids
(University of Waterloo, 2021-08-27)In this thesis, two classes of binary matroids will be discussed: even-cycle and even-cut matroids, together with problems which are related to their graphical representations. Even-cycle and even-cut matroids can be ... -
Resolution of Ties in Parametric Quadratic Programming
(University of Waterloo, 2004)We consider the convex parametric quadratic programming problem when the end of the parametric interval is caused by a multiplicity of possibilities ("ties"). In such cases, there is no clear way for the proper active ... -
Results on Chromatic Polynomials Inspired by a Correlation Inequality of G.E. Farr
(University of Waterloo, 2018-09-25)In1993 Graham Farr gave a proof of a correlation inequality involving colourings of graphs. His work eventually led to a conjecture that number of colourings of a graph with certain properties gave a log-concave sequence. ... -
Revisiting the security model for aggregate signature schemes
(University of Waterloo, 2014-05-26)Aggregate signature schemes combine the digital signatures of multiple users on different messages into one single signature. The Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signature scheme is one such scheme, based on ... -
Rigidity of near-optimal superdense coding protocols
(University of Waterloo, 2023-09-19)Rigidity in quantum information theory refers to the stringent constraints underlying optimal or near-optimal performance in certain quantum tasks. This property plays a crucial role in verifying untrusted quantum devices ... -
Routing, Scheduling, and Sorting in Consolidated Networks
(University of Waterloo, 2024-04-25)Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes ... -
Sandwich and probe problems for excluding paths
(Elsevier, 2018-12-31)Let Pk denote an induced path on k vertices. For k ≥ 5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k ≤ 4, it is known that the Pk-free sandwich ... -
The Sandwich Problem for Decompositions and Almost Monotone Properties
(Springer Nature, 2018)We consider the graph sandwich problem and introduce almost monotone properties, for which the sandwich problem can be reduced to the recognition problem. We show that the property of containing a graph in C as an induced ... -
Santa Claus, Machine Scheduling and Bipartite Hypergraphs
(University of Waterloo, 2020-01-10)Here we discuss two related discrete optimization problems, a prominent problem in scheduling theory, makespan minimization on unrelated parallel machines, and the other a fair allocation problem, the Santa Claus problem. ... -
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 ... -
The search for an excluded minor characterization of ternary Rayleigh matroids
(University of Waterloo, 2008-01-24)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 ...