Browsing Combinatorics and Optimization by Title
Now showing items 404-423 of 436
-
SUBMODULAR FUNCTIONS, GRAPHS AND INTEGER POLYHEDRA
(University of Waterloo, 2016-09-12)This thesis is a study of the faces of certain combinatorially defined polyhedra. In particular, we examine the vertices and facets of these polyhedra. Chapter 2 contains the essential mathematical background in polyhedral ... -
Sum-of-norms clustering: theoretical guarantee and post-processing
(University of Waterloo, 2020-09-11)Sum-of-norms clustering is a method for assigning n points in d-dimensional real space to K clusters, using convex optimization. Recently, Panahi et al. proved that sum-of-norms clustering is guaranteed to recover a mixture ... -
A Survey of Attacks on Multivariate Cryptosystems
(University of Waterloo, 2005)This thesis provides a survey of the attacks on multivariate cryptosystems. We begin by providing an outline of the general multivariate cryptosystem. Proceeding from there, we show that even with this level of detail, ... -
A survey of the trust region subproblem within a semidefinite framework
(University of Waterloo, 2000)Trust region subproblems arise within a class of unconstrained methods called trust region methods. The subproblems consist of minimizing a quadratic function subject to a norm constraint. This thesis is a survey of ... -
A survey on Traitor Tracing Schemes
(University of Waterloo, 2000)When intellectual properties are distributed over a broadcast network, the content is usually encrypted in a way such that only authorized users who have a certain set of keys, can decrypt the content. Some authorized ... -
Symmetries
(University of Waterloo, 2016-10-03)Automorphisms of graphs, hypergraphs and disgraphs are investigated. The invariance of the chromatic polynomial in the rotor effect is disproved. New invariance results are obtained. It is shown that given any integer k ... -
Techniques for Proving Approximation Ratios in Scheduling
(University of Waterloo, 2010-09-30)The problem of finding a schedule with the lowest makespan in the class of all flowtime-optimal schedules for parallel identical machines is an NP-hard problem. Several approximation algorithms have been suggested for ... -
Techniques of Side Channel Cryptanalysis
(University of Waterloo, 2001)The traditional model of cryptography examines the security of cryptographic primitives as mathematical functions. This approach does not account for the physical side effects of using these primitives in the real world. ... -
Technology Diffusion on Spiders
(University of Waterloo, 2017-08-29)There has been significant research about cascade effects that occur when information is spread through a network. Most models of such cascade effects are highly-localised, which means that they assume a node’s behaviour ... -
Theory of measurement-based quantum computing
(University of Waterloo, 2008-12-10)In the study of quantum computation, data is represented in terms of linear operators which form a generalized model of probability, and computations are most commonly described as products of unitary transformations, which ... -
Thin Trees in Some Families of Graphs
(University of Waterloo, 2018-04-25)Let 𝐺=(𝑉,𝐸) be a graph and let 𝑇 be a spanning tree of 𝐺. The thinness parameter of 𝑇 denoted by 𝜌(𝑇) is the maximum over all cuts of the proportion of the edges of 𝑇 in the cut. Thin trees play an important role ... -
Thomassen’s 5-Choosability Theorem Extends to Many Faces
(University of Waterloo, 2021-09-10)We prove in this thesis that planar graphs can be L-colored, where L is a list-assignment in which every vertex has a 5-list except for a collection of arbitrarily large faces which have 3-lists, as long as those faces ... -
Tolls For Atomic Congestion Games
(University of Waterloo, 2021-02-26)In games where selfish players compete for resources, they often arrive at equilibria that are less desirable than the social optimum. To combat this inefficiency, it is common for some central authority to place tolls on ... -
Towards Erdős-Hajnal for Graphs with No 5-Hole
(Springer Nature, 2019-11-01)The Erdős-Hajnal conjecture says that for every graph H there exists c > 0 such that max(α(G), w(G)) ≥ nc for every H-free graph G with n vertices, and this is still open when H = C5. Until now the best bound known on ... -
Towards Private Biometric Authentication and Identification
(University of Waterloo, 2023-09-05)Handwriting and speech are important parts of our everyday lives. Handwriting recognition is the task that allows the recognizing of written text, whether it be letters, words or equations, from given data. When analyzing ... -
Transitive Factorizations of Permutations and Eulerian Maps in the Plane
(University of Waterloo, 2005)The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800's. This problem translates combinatorially into factoring a permutation with a specified cycle ... -
Transmitting Quantum Information Reliably across Various Quantum Channels
(University of Waterloo, 2013-05-01)Transmitting quantum information across quantum channels is an important task. However quantum information is delicate, and is easily corrupted. We address the task of protecting quantum information from an information ... -
Transversal Problems In Sparse Graphs
(University of Waterloo, 2022-09-20)Graph transversals are a classical branch of graph algorithms. In such a problem, one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs~$F$ from a fixed family ... -
The Traveling Tournament Problem
(University of Waterloo, 2022-08-17)In this thesis we study the Traveling Tournament problem (TTP) which asks to generate a feasible schedule for a sports league such that the total travel distance incurred by all teams throughout the season is minimized. ... -
Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable
(Wiley, 2019-10)We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vušković.