Now showing items 21-40 of 433

    • Applications of Stochastic Gradient Descent to Nonnegative Matrix Factorization 

      Slavin, Matthew (University of Waterloo, 2019-07-15)
      We consider the application of stochastic gradient descent (SGD) to the nonnegative matrix factorization (NMF) problem and the unconstrained low-rank matrix factorization problem. While the literature on the SGD algorithm ...
    • Applied Hilbert's Nullstellensatz for Combinatorial Problems 

      Romero Barbosa, Julian (University of Waterloo, 2016-09-23)
      Various feasibility problems in Combinatorial Optimization can be stated using systems of polynomial equations. Determining the existence of a \textit{stable set} of a given size, finding the \textit{chromatic number} of ...
    • Approximate Private Quantum Channels 

      Dickinson, Paul (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 &epsilon;-randomizing maps, <em>n</em> + 2log(1/&epsilon;) + <em>c</em> ...
    • Approximately Coloring Graphs Without Long Induced Paths 

      Chudnovsky, Maria; Schaudt, Oliver; Spirkl, Sophie; stein, maya; Zhong, Mingxian (Springer Nature, 2017)
      It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable ...
    • Approximately Coloring Graphs Without Long Induced Paths 

      Chudnovsky, Maria; Schaudt, Oliver; Spirkl, Sophie; stein, maya; Zhong, Mingxian (Springer Nature, 2019)
      It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable ...
    • Approximating Minimum-Size 2-Edge-Connected and 2-Vertex-Connected Spanning Subgraphs 

      Narayan, Vishnu Verambudi (University of Waterloo, 2017-04-27)
      We study the unweighted 2-edge-connected and 2-vertex-connected spanning subgraph problems. A graph is 2-edge-connected if it is connected on removal of an edge, and it is 2-vertex-connected if it is connected on removal ...
    • Approximation Algorithms for (S,T)-Connectivity Problems 

      Laekhanukit, Bundit (University of Waterloo, 2010-08-03)
      We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex ...
    • Approximation Algorithms for Clustering and Facility Location Problems 

      Ahmadian, Sara (University of Waterloo, 2017-04-06)
      Facility location problems arise in a wide range of applications such as plant or warehouse location problems, cache placement problems, and network design problems, and have been widely studied in Computer Science and ...
    • Approximation Algorithms for Distributionally Robust Stochastic Optimization 

      Linhares Rodrigues, Andre (University of Waterloo, 2019-05-15)
      Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: ...
    • Approximation Algorithms for Graph Protection Problems 

      Lange, Alexander (University of Waterloo, 2015-05-22)
      We study a budgeted cut problem known as Graph Protection, where the goal is to remove edges of a given graph in order to protect valuable nodes from stochastic, infectious threats. This problem was recently proposed ...
    • Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations 

      Gao, Zhihan (University of Waterloo, 2015-07-29)
      Linear programming (LP) relaxations provide a powerful technique to design approximation algorithms for combinatorial optimization problems. In the first part of the thesis, we study the metric s-t path Traveling Salesman ...
    • Aspects of Quantum Field Theory in Enumerative Graph Theory 

      Yusim, Samuel (University of Waterloo, 2022-10-24)
      While a quantum field theorist has many uses for mathematics of all kinds, the relationship between quantum field theory and mathematics is far too fluid in the world of modern research to be described as the simple provision ...
    • Assessing the Trainability of the Variational Quantum State Diagonalization Algorithm at Scale 

      Arrow, Joan (University of Waterloo, 2022-04-28)
      Quantum algorithm development is a famously difficult problem. The lack of intuition concerning the quantum realm makes constructing quantum algorithms which solve partic- ular problems of interest difficult. In addition, ...
    • Augmenting Trees to Achieve 2-Node-Connectivity 

      Grout, Logan (University of Waterloo, 2020-09-02)
      This thesis focuses on the Node-Connectivity Tree Augmentation Problem (NC-TAP), formally defined as follows. The first input of the problem is a graph G which has vertex set V and edge set E. We require |V| >= 3 to avoid ...
    • Batch Verification of Elliptic Curve Digital Signatures 

      Wesolowski, Michael (University of Waterloo, 2015-04-20)
      This thesis investigates the efficiency of batching the verification of elliptic curve signatures. The first signature scheme considered is a modification of ECDSA proposed by Antipa et al.\ along with a batch verification ...
    • Bi-objective short-term scheduling in a rolling horizon framework: a priori approaches with alternative operational objectives 

      Lee, Do Yeon; Fukasawa, Ricardo; Ricardez-Sandoval, Luis (Elsevier, 2019-11)
      This study addresses short-term scheduling problems with throughput and make-span as conflicting objectives, focusing on a priori multi-objective methods. Two contributions are presented. The first contribution is to propose ...
    • Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two 

      Held, Stephan; Spirkl, Sophie (Association for Computing Machinery, 2018-01)
      We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where ...
    • Bipartite Distance-Regular Graphs of Diameter Four 

      Huang, Junbo (University of Waterloo, 2014-08-11)
      Using a method by Godsil and Roy, bipartite distance-regular graphs of diameter four can be used to construct $\{0,\alpha\}$-sets, a generalization of the widely applied equiangular sets and mutually unbiased bases. In ...
    • Bipartite Quantum Walks and the Hamiltonian 

      Chen, Qiuting (University of Waterloo, 2023-09-26)
      We study a discrete quantum walk model called bipartite walks via a spectral approach. A bipartite walk is determined by a unitary matrix U, i.e., the transition matrix of the walk. For every transition matrix U, there is ...
    • A Blueprint for Semidefinite Relaxations of Binary-Constrained Quadratic Programs Computing tight bounds on NP-hard problems using ADMM 

      Graham, Naomi (University of Waterloo, 2020-12-18)
      This thesis looks at the solution techniques of two NP-hard, large scale problems, the quadratic assignment problem, QAP, and the side chain positioning, SCP, problem. We summarize existing approaches from and look at the ...

      UWSpace

      University of Waterloo Library
      200 University Avenue West
      Waterloo, Ontario, Canada N2L 3G1
      519 888 4883

      All items in UWSpace are protected by copyright, with all rights reserved.

      DSpace software

      Service outages