Thesis (M.Sc.). / Written for the Dept. of Mathematics and Statistics. Title from title page of PDF (viewed 2008/05/29). Includes bibliographical references.

No description available.

Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. In this paper, we show the exact spanning ratio of the parallelogram Delaunay graph, making the parallelogram the fifth convex shape for which an exact bound is known. The worst-case spanning ratio is exactly $$\frac{\sqrt{2}\sqrt{1+A^2+2A\cos(\theta_0)+(A+\cos(\theta_0))\sqrt{1+A^2+2A\cos(\theta_0)}}}{\sin(\theta_0)},$$ where A is the aspect ratio and θ_0 is the non-obtuse angle of the parallelogram. Moreover, we show how to construct a parallelogram Delaunay graph whose spanning ratio matches the above mentioned spanning ratio.

As public agencies have implemented programs to respond to natural disasters, alleviate poverty, provide food security, and address other wicked problems, the organizational structuring of public sector program management has changed in response. The federal agencies responsible for U.S. foreign policy, including the United States Agency for International Development (USAID), have embraced multi-organizational, cross-sector network collaboration as part of their core missions. The strategic transition of USAID to an increased use of network models for program implementation raises questions concerning the ability of the agency, through its partners, to foster organizational learning in this network setting. Ensuring the ability to utilize knowledge and ways of knowing generated through program activity is a critical factor to sustaining the long-term capacity of government agencies and their partners to pursue solutions for these complex global problems. The research reported in this dissertation focuses on network administrative organizations (NAOs) delegated official responsibility for the management of government-funded multi-institutional programs, to understand how organizational learning for innovation takes place in an NAO-led network. This research explored the USAID Feed the Future Innovation Labs for Collaborative Research program focusing on two comparable case studies representative of NAO-led goal-directed networks, the Integrated Pest Management and Horticulture Innovation Labs. The Crossan et al. (1999) 4I framework on organizational learning served as the primary theoretical foundation for addressing how NAOs enable, manage, and leverage organizational learning associated with the boundary work of their program team representatives to innovate as networks. In the two cases studied, the findings indicated that learning practices flowed as anticipated within and across the program network for program and administrative related knowledge, but flowed in a number of different directions for knowledge related to addressing novel problems. Additionally, the NAOs' ability to institutionalize knowledge generated through the work of program teams and individual members followed unpredictable patterns and was influenced by the presence of knowledge and learning boundaries within the network. The research contribution includes a theorized two-part role for NAOs associated with managing situational learning on behalf of the network and a proposed expansion of the 4I framework that incorporates a network level of learning, organizational boundaries, and two new processes introduced as a result of the findings. Finally, the research concludes with a proposed a preliminary framework beneficial to NAO practitioners tasked with managing organizational learning in similar goal-directed network environments. / PHD / As public agencies have implemented programs to respond to natural disasters, alleviate poverty, provide food security, and address other wicked problems, federal agencies like the United States Agency for International Development (USAID) have embraced multi-organizational, cross-sector collaboration, through an increased use of network models for program implementation. This raises questions concerning the ability of the agency, through its partners, to foster organizational learning in a network setting. Ensuring the ability to utilize knowledge and ways of knowing generated through program activity is vital to sustaining the long-term capacity of government agencies and their partners to pursue solutions for global problems. The dissertation focuses on network administrative organizations (NAOs) delegated official responsibility for the management of government-funded multi-institutional programs, to understand how organizational learning for innovation takes place in an NAO-led network. This research explored the USAID Feed the Future Innovation Labs for Collaborative Research program focusing on two comparable case studies representative of NAO-led goal-directed networks, the Integrated Pest Management and Horticulture Innovation Labs. The Crossan et al. (1999) 4I framework on organizational learning served as the primary theoretical foundation for addressing how NAOs enable, manage, and leverage organizational learning associated with the boundary work of their program team representatives to innovate as networks. In the two cases studied, the findings indicated that learning practices flowed as anticipated within and across the program network for program and administrative related knowledge, but flowed in a number of different directions for knowledge related to addressing novel problems. Additionally, the NAOs’ ability to institutionalize knowledge generated through the work of program teams and individual members followed unpredictable patterns and was influenced by the presence of knowledge and learning boundaries within the network. The research contribution includes a theorized two-part role for NAOs associated with managing situational learning on behalf of the network and a proposed expansion of the 4I framework that incorporates a network level of learning, organizational boundaries, and two new processes introduced as a result of the findings. Finally, the research concludes with a proposed preliminary framework beneficial to NAO practitioners tasked with managing organizational learning in similar goal-directed network environments.

This study tested the existence of significant differences in levels of perceived job stressors between non-managerial individuals in boundary-spanning and nonboundary- spanning occupations. Correlations between selected demographic characteristics and levels of perceived job stressors were also determined.

In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \begin{enumerate} \item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\log^2n)$ time. For a cut $(U, V\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \leq x \leq 2K$ with high probability in $O(|U|\log n)$ time. \item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\text{polylog}(n))$. For each node $v$ we require memory of size $\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \end{enumerate} / Graduate / 0984 / b_mountjoy9@hotmail.com

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

This term project deals with the functionality of Spanning Tree protocols, especially the Rapid Spanning Tree Protocol, and the Multiple Spanning Tree Protocol. The primary usage of spanning tree protocols is the prevention of loops within the data link layer, the prevention of a broadcast storm, and also dealing with redundancy in the network. Moreover, the project contains the description of configuration of these protocols on Cisco devices. The main goal of this thesis is to implement the Multiple Spanning Tree protocol into INET framework within the OMNeT++ simulation system. Then, the implemented solution is tested and it's functionality is compared with the referential behavior in a Cisco network.

In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case. Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one. We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval. Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set. We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable. Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set. Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.