Browsing Combinatorics and Optimization by Title
Now showing items 389-408 of 436
-
Solving Saddle Point Formulations of Linear Programs with Frank-Wolfe
(University of Waterloo, 2023-08-24)The problem of solving a linear program (LP) is ubiquitous in industry, yet in recent years the size of linear programming problems has grown and continues to do so. State-of-the-art LP solvers make use of the Simplex ... -
Some Upper and Lower Bounds regarding Query Complexity
(University of Waterloo, 2017-08-29)Query complexity is one of the several notions of complexity de ned to measure the cost of algorithms. It plays an important role in demonstrating the quantum advantage, that quantum computing is faster than classical ... -
Sparsity in Critical Graphs with Small Clique Number
(University of Waterloo, 2020-08-27)In 1998, Reed conjectured that for every graph $G$, $\chi(G) \leq \lceil \frac{1}{2}(\Delta(G)+1+\omega(G)) \rceil$, and proved that there exists $\varepsilon > 0$ such that $\chi(G) \leq \lceil (1 - \varepsilon)(\Delta(G)+1) ... -
Spectral Aspects of Cocliques in Graphs
(University of Waterloo, 2014-05-01)This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns ... -
Spectral Properties of Structured Kronecker Products and Their Applications
(University of Waterloo, 2019-05-01)We study certain spectral properties of some fundamental matrix functions of pairs of symmetric matrices. Our study includes eigenvalue inequalities and various interlacing properties of eigenvalues. We also discuss the ... -
Spectral properties of tensor products of channels
(Elsevier, 2018-09-15)We investigate spectral properties of the tensor products of two completely positive and trace preserving linear maps (also known as quantum channels) acting on matrix algebras. This leads to an important question of when ... -
Split Cuts From Sparse Disjunctions
(University of Waterloo, 2019-01-16)Cutting planes are one of the major techniques used in solving Mixed-Integer Linear Programming (MIP) models. Various types of cuts have long been exploited by MIP solvers, leading to state-of-the-art performance in practice. ... -
A Stability Theorem for Matchings in Tripartite 3-Graphs
(Cambridge University Press, 2018-04-02)It follows from known results that every regular tripartite hypergraph of positive degree, with n vertices in each class, has matching number at least n/2. This bound is best possible, and the extremal configuration is ... -
Stabilizing Weighted Graphs
(University of Waterloo, 2017-08-29)An edge-weighted graph G = (V,E) is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in some interesting game theory ... -
State Transfer & Strong Cospectrality in Cayley Graphs
(University of Waterloo, 2022-08-09)This thesis is a study of two graph properties that arise from quantum walks: strong cospectrality of vertices and perfect state transfer. We prove various results about these properties in Cayley graphs. We consider ... -
Stochastic Minimum Norm Combinatorial Optimization
(University of Waterloo, 2022-07-28)Motivated by growing interest in optimization under uncertainty, we undertake a systematic study of designing approximation algorithms for a wide class of 1-stage stochastic-optimization problems with norm-based objective ... -
STPA-Sec Applied to Path Planning: Quantum-Safe Autonomous Vehicles
(University of Waterloo, 2022-05-12)Autonomous vehicles and quantum computers are two emerging technologies that will transform our world in the not-too-distant future. This thesis examines the safety and security of autonomous vehicles in a world where ... -
Structure in Stable Matching Problems
(University of Waterloo, 2016-12-14)In this thesis we provide two contributions to the study of structure in stable matching problems. The first contribution is a short new proof for the integrality of Rothblum’s linear description of the convex hull of ... -
A Study of Time Representation in a Class of Short Term Scheduling Problems
(University of Waterloo, 2016-08-17)The problem of scheduling operations has received significant attention from academia and industrial practitioners in the past few decades. A key decision in various scheduling operations problems is when to perform an ... -
Subdividing the cd-index
(University of Waterloo, 2016-04-28)This thesis aims to give the reader an introduction and overview of the cd-index of a poset, as well as establish some new results. We give a combinatorial proof of Ehrenborg and Karu's cd-index subdivision decomposition ... -
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 ...