<p>The global routing problem is becoming more and more important in the design of today's integrated circuits. A small chip may contain up to millions of components and wires. Although global routing can be formulated as an integer linear programming problem, it is hard to solve directly using currently available solvers. We discuss a relaxation of the problem to a linear programming (LP) formulation with a fractional solution. However, the relaxation yields an NP-hard problem. In this thesis, we introduce three relaxations: the primal (<em>Pc</em>), the Lagrange dual (<em>Dc</em>), and the unimodular (<em>PI</em>) formulation. At optimality, all three problems have the same objective value. A new way to tackle the LP problem is introduced: first solve the <em>Dc</em> and try to find Lagrange multipliers in order to build the <em>PI</em> model, from which an integer solution can be obtained directly. An implementation based on the discussed approaches was tested using IBM benchmarks.</p> / Master of Applied Science (MASc)

<p>This thesis considers the Shannon capacity of multiuser multiple input multiple output (MIMO) wireless communication systems. That is, the fundamental limit on the rates at which data can be reliably communicated. The focus is on scenarios in which the channel has long coherence times and perfect channel state information is available to both transmitters and receivers. The thesis considers two important design problems in multiuser MIMO wireless communication systems: the design of the sumrate optimal input distribution for the MIMO multiple access channel (MIMO MAC), and the design of the sum-rate optimal input distribution for the MIMO broadcast channel (MIMO BC).</p> <p>The thesis considers algorithms for solving these design problems that are based on the principle of iterative water-filling. The contributions of the thesis are twofold. First, a correct and rigorous proof of convergence of the family of water-filling algorithms is derived. This proof overcomes weaknesses in the previous attempts of others to prove convergence. Second, an efficient algorithm is presented for the water-filling procedure that lies at the heart of the iterative water-filling algorithm. This algorithm will open the door for further efficient utilization of the iterative water-filling algorithm. This novel algorithm is based on the principle of Fibonacci search, and since the iterative water filling algorithm involves repeated water-filling procedures, the impact of this efficient algorithm is magnified.</p> <p>The outcomes of this research are that the iterative water-filling algorithms are mathematically validated for the above-mentioned design problems in multiuser MIMO wireless communication systems, and that the implementation of these algorithms is made more efficient through the application of the efficient Fibonacci search method for the underlying water-filling procedure.</p> / Master of Applied Science (MASc)

<p>Why sexual reproduction and recombination are prevalent among living organisms is one of the most intriguing questions in biology. It has been studied extensively from a multitude of perspectives ranging from multi-locus population genetics models, in-vivo and more recently in-silico systems. The analysis of complex metabolic networks in living organisms reveals that they can be decomposed into several functionally distinct sub-groups, called modules. This property of modular organization has been accepted as a general organizational feature of biological networks, and has important consequences for the evolution of biologically complex features through different combinations of simpler functions. In this light it has been shown that sexual populations can develop a form of modularity on the genetic level, called mixability, where alleles are selected for their ability to function under a wide variety of genetic contexts, much like a module.</p> <p>However the functional implications of mixability still remain to be seen. We wish to assess whether mixability can develop in a simplified model of populations undergoing evolution for increased biological complexity through the construction of their genomes into simple metabolic chains. We modelled the fitness and growth of complexity in sexual and asexual populations in the presence of recurrent mutations which increase the ability of genes to interact with one another. Our results show that mixability is selected for in sexual populations when genetic diversity is high and under certain conditions gives sexual populations a competitive edge over asexual populations through increased genetic complexity. This provides a starting point for examining the effect of mixability upon growing genetic networks and its role in influencing larger scale modularity, which thus far has not been significantly explored.</p> / Master of Science (MS)

<p>This thesis provides a Fully Polynomial Time Approximation Scheme (FPTAS) for the minimum total weighted tardiness (TWT) problem with a constant number ofdistinct due dates.</p> <p>Given a sequence ofjobs on a single machine, each with a weight, processing time, and a due date, the tardiness of a job is the amount of time that its completion time goes beyond its due date. The TWT problem is to find a schedule of the given jobs such that the total weighted tardiness is minimized. This problem is NP-hard even when the number of distinct due dates is fixed. In this thesis, we present a dynamic programming algorithm for the TWT problem with a constant number of distinct due dates first and then adopt a rounding scheme to obtain an FPTAS.</p> <p>Three major points that we make in this algoritlun are: we observe a series of structural properties of optimal schedules so that we shrink the state space of the DP; we make use of preemption (i.e. allowing the processing of a job to be interrupted and restarted later) for the design of the DP; the rounding scheme that we adopt guarantees that a factor 1+ ℇ of the optimal solution is generated and the algorithm runs within a polynomial time of the problem size.</p> / Master of Applied Science (MASc)