This study describes algorithms for the solution of several single facility location problems with maximin or minimax objective functions. Interactive computer graphical algorithms are presented for maximizing the minimum rectilinear travel distance and for minimizing the maximum rectilinear travel distance to a number of point demands when there exist several right-angled polygonal barriers to travel. For the special case of unweighted rectilinear distances with barriers, a purely numerical algorithm for the maximin location problem is described. An interactive computer graphical algorithm for maximizing the minimum Euclidean, rectilinear, or general 1p distance to a number of polygonal areas is described. A modified version of this algorithm for location problems with the objective of minimizing the maximum cost when the costs are non-linear monotonically decreasing functions of distance is presented. Extension of this algorithm to problems involving the minimization of the maximum cost when the costs are functions of both distance and direction is discussed using asymmetric distances. / Thesis / Doctor of Philosophy (PhD)

No description available.

A Julia set for a complex function 𝑓 is the set of all points in the complex plane where the iterates of 𝑓 do not form a normal family. A picture of the Julia set for a function can be generated with a computer by coloring pixels (which we consider to be small squares) based on the behavior of the point at the center of each pixel. We consider the accuracy of computer generated pictures of Julia sets. Such a picture is said to be accurate if each colored pixel actually contains some point in the Julia set. We extend previous work to show that the pictures generated by an algorithm for the family λe² are accurate, for appropriate choices of parameters in the algorithm. We observe that the Julia set for meromorphic functions with polynomial Schwarzian derivative is the closure of those points which go to infinity under iteration, and use this as a basis for an algorithm to generate pictures for such functions. A pixel in our algorithm will be colored if the center point becomes larger than some specified bound upon iteration. We show that using our algorithm, the pictures of Julia sets generated for the family λtan(z) for positive real λ are also accurate. We conclude with a cautionary example of a Julia set whose picture will be inaccurate for some apparently reasonable choices of parameters, demonstrating that some care must be exercised in using such algorithms. In general, more information about the nature of the function may be needed. / Ph. D.

We present a variety of exact and parameterized algorithms for Subset Sum and otherrelated problems. The major contributions of this thesis include: 1. Average-case algorithms for Generalized Subset Sum, the problem that generalizes both Subset Sum and Equal Subset Sum, as well as structural results describing the parameter regime in which solutions exist. These results extend the application of the “Representation Method” and are the fastest known in this setting. 2. A proof that Either-Or Subset Sum, the problem of solving either Subset Sum or Equal Subset Sum, can be solved exponentially faster than time 2⁰‧⁵ⁿ in the worst case. In our view, this result illustrates the potential of the “structure vs. randomness” approach for Subset Sum. 3. Algorithms that solve worst-case Subset Sum faster than time 2⁰‧⁵ⁿ by a polynomial factor. These improvements on the best known exact algorithms for Subset Sum represent the successful application of “log shaving” techniques to the problem. 4. Algorithms for Subset Sum and k-SUM with constant doubling. When considered in terms of a novel parameterization in the doubling constant, Subset Sum admits an XP-algorithm, while k-SUM is Fixed-Parameter Tractable. We also show that Subset Sum is FPT in the doubling constant if and only if an instance I of Hyperplane-Constrained Integer Linear Programming with n variables, m constraints, and constraint matrix entries bounded by ∆ can be solved in time ∆^{O(m)} · poly(|I|).

No description available.

No description available.

No description available.

Targeted software testing is a critical task in development of secure software. The core challenge of targeted software testing is to generate many inputs that reach specific code target locations in a given program. However, this task is challenging because it is NP-hard in theory and real-world programs contain very large input spaces and many lines of code, making this difficult in practice. In this thesis, I introduce a new approach for targeted software testing based on adaptive sampling. The key insight is to reduce the original problem to a sequence of approximate counting problems, and I apply this approach to targeted software testing in two stages. First, to find a single target-reaching input when no such input is given, I develop a new search algorithm MC2 that adaptively uses approximate-count feedback to narrow down which input region is more likely to contain a target-reaching input using probabilistic bisection. Second, given a single target-reaching input, I develop a new set approximation algorithm ProgramSampler that adaptively learns an approximation of the set of target-reaching inputs based on approximate-count feedback, where the set approximation can be efficiently uniformly sampled for many target-reaching inputs. Backed by theoretical guarantees, these techniques have been highly effective in practice: outperforming existing methods on average by 1-2 orders of magnitude.

Thesis (PhD (Logistics))--University of Stellenbosch, 2007. / In this dissertation original algorithms are introduced to solve separable resource allocation problems (RAPs) with increasing nonlinear functions in the objective function, and lower and upper bounds on each variable. Algorithms are introduced in three special cases. The first case arises when the objective function of the RAP consists of the sum of convex functions and all the variables for these functions range over the same interval. In the second case RAPs with the sum of convex functions in the objective function are considered, but the variables of these functions can range over different intervals. In the last special case RAPs with an objective function comprising the sum of convex and concave functions are considered. In this case the intervals of the variables can range over different values. In the first case two new algorithms, namely the fraction and the slope algorithm are presented to solve the RAPs adhering to the conditions of the case. Both these algorithms yield far better solution times than the existing branch and bound algorithm. A new heuristic and three new algorithms are presented to solve RAPs falling into the second case. The iso-bound heuristic yields, on average, good solutions relative to the optimal objective function value in faster times than exact algorithms. The three algorithms, namely the iso-bound algorithm, the branch and cut algorithm and the iso-bound branch and cut algorithm also yield considerably beter solution times than the existing branch and bound algorithm. It is shown that, on average, the iso-bound branch and cut algorithm yields the fastest solution times, followed by the iso-bound algorithm and then by die branch and cut algorithm. In the third case the necessary and sufficient conditions for optimality are considered. From this, the conclusion is drawn that search techniques for points complying with the necessary conditions will take too long relative to branch and bound techniques. Thus three new algorithms, namely the KL, SKL and IKL algorithms are introduced to solve RAPs falling into this case. These algorithms are generalisations of the branch and bound, branch and cut, and iso-bound algorithms respectively. The KL algorithm was then used as a benchmark. Only the IKL algorithm yields a considerable improvement on the KL algorithm.

Large-scale heterogeneous distributed computing environments (such as Computational Grids and Clouds) offer the promise of access to a vast amount of computing resources at a relatively low cost. In order to ease the application development and deployment on such complex environments, high-level parallel programming languages exist that need to be supported by sophisticated runtime systems. One of the main problems that these runtime systems need to address is dynamic load balancing that ensures that no resources in the environment are underutilised or overloaded with work. This thesis deals with the problem of obtaining good speedups for irregular applications on heterogeneous distributed computing environments. It focuses on workstealing techniques that can be used for load balancing during the execution of irregular applications. It specifically addresses two problems that arise during work-stealing: where thieves should look for work during the application execution and how victims should respond to steal attempts. In particular, we describe and implement a new Feudal Stealing algorithm and also we describe and implement new granularity-driven task selection policies in the SCALES simulator, which is a work-stealing simulator developed for this thesis. In addition, we present the comprehensive evaluation of the Feudal Stealing algorithm and the granularity-driven task selection policies using the simulations of a large class of regular and irregular parallel applications on a wide range of computing environments. We show how the Feudal Stealing algorithm and the granularity-driven task selection policies bring significant improvements in speedups of irregular applications, compared to the state-of-the-art work-stealing algorithms. Furthermore, we also present the implementation of the task selection policies in the Grid-GUM runtime system [AZ06] for Glasgow Parallel Haskell (GpH) [THLPJ98], in addition to the implementation in SCALES, and we also present the evaluation of this implementation on a large set of synthetic applications.