Thesis (Ph. D.)--University of Wisconsin--Madison, 1981. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 171-175).

Thesis (M.S.)--University of Wisconsin--Madison, 1963. / Typescript. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaf 66).

Techniques for the heuristic and exact two-level minimization of Boolean and multivalued functions are presented. The work is based on a previously existing algorithmic framework for two-level minimization known as directed search. This method is capable of selecting covering prime implicants without generating all of them. Directed search differs from most other minimization methods in that implicant cubes are generated from minterms, not from other cubes. Heretofore, the directed search algorithm and published variants have not been capable of minimizing PLA’s of “industrial” size. The algorithms in this Work significantly ameliorate this situation. In particular, original and efficient techniques are proposed for prime implicant generation, computation of dominance relations, elimination of redundant minterms, storage and retrieval of cubes and minterms, and, isolation and reduction of cycles. The algorithms are embodied in a working minimizer called MDSA. In the absence of cycles, MDSA provides provably optimum cube covers. Empirical comparison with other minimizers show the new algorithms to be very competitive, even superior. For mid-sized non-cyclic PLA’s, MDSA is nearly always faster, and usually faster for PLA’s containing cycles, than the best known heuristic competitor. The number of cubes found for cyclic PLA’s is also better (lower), on average. MDSA can also be set to provide provably minimum solutions for cyclic functions. In this case, MDSA again outperforms competitive minimizers in a similar mode of operation. Both heuristic and exact versions of MDSA are restricted to PLA’s with. 32 or fewer inputs, and 32 or fewer outputs. / Graduate

The selection of updating formulas for the H matrix and the subproblem of one-dimensional search are considered for variable metric algorithms not using exact linear searches in the subproblem. It is argued that the convex class of updating formulas given by Fletcher is the logical choice for such algorithms. It is shown that direct linear searches are more efficient than linear searches using directional derivatives at each point, particularly for objective functions of many variables. Features of algorithms using the convex class of formulas without exact searches are discussed. It is proven that effects on these algorithms of scaling of the variables of the objective function are identical to effects of transforming the initial H matrix. It is predicted that regions of a function where the Hessian is non-positive definite may be detrimental to convergence of these algorithms. A function is given for which Fletcher's recent algorithm (which does not use any linear search for a minimum) fails to converge. Attempts were made to devise a test to detect non-convexity of a function so that an algorithm using no linear search for a minimum in convex regions and an alternative strategy in non-convex regions could be developed to overcome this problem. Algorithms incorporating a test for non-convexity were coded as well as Fletcher's algorithm, an algorithm using a weak quadratic direct minimizing search, and an algorithm using the weak cubic minimizing search as used in the Fletcher Powell method. Numerical experiments were performed on functions from the literature and functions developed by the author. Fletcher's algorithm was found to be inefficient on all functions in comparison to the weak quadratic search algorithm where the initial H matrix had small eigenvalues. Where Fletcher's algorithm was relatively efficient, the former search was in all cases competitive. The value of a direct over derivative linear search is demonstrated. The algorithms using a test for convexity were not effective, since the best was not generally"effective in detecting non-convexity. It is concluded that algorithms without a form of one-dimensional weak minimizing search are not suitable for use on general minimization problems, and that the weak quadratic direct search proposed is a more efficient and reliable alternative. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

This dissertation has two main objectives: first, to develop efficient algorithms for the solution of one and two period constrained optimization problems, and second, to apply these methods to the solution of portfolio selection and revision problems. The algorithms developed are based upon the Frank-Wolfe method. A convergent algorithm is developed which modifies this approach to allow for sequences of approximations to the objective and to the gradient of the objective, as well as inexact linear searches. By utilizing varying degrees of accuracy (with increasing precision as the optimum is approached), the method will be computationally more tractable than fixed tolerance methods without sacrificing the convergence properties. This algorithm is then applied to a static portfolio selection problem. Here the investor has a wealth allotment to be allocated to a number of possible risky investments with the objective of maximizing the expected utility of terminal wealth. The investor's preferences are assumed to be given by a (von-Neumann-Morgenstern) utility function. For the empirical studies seven classes of utility functions and ten joint normally distributed assets are used. One question investigated is the degree to which the Arrow-Pratt risk aversion measure determines portfolio composition. The empirical results are augmented by a theorem showing (for normally distributed security returns) that the Rubinstein global risk aversion measure is sufficient to determine portfolio composition. The second part of this dissertation deals with two period problems. An algorithm, based on the method of Hogan for extremal value functions, is developed. The extensions (and subsequent advantages) are analogous to those developed for the one period problem. This method is used to solve a portfolio revision problem utilizing five joint normally distributed assets and proportional transaction costs. Empirically, it is shown that significant errors are generated by ignoring the revision aspect of the problem, even with serially uncorrelated returns. / Business, Sauder School of / Graduate

No description available.

No description available.

For a weighted graph with n vertices and m edges, the Minimum k-Way Cut problem is to find a partition of the vertices into k sets that minimizes the total weight of edges crossing the sets. We obtain several important structural properties of minimum multiway cuts and use them to design efficient algorithms for several multiway partition problems. We design the first algorithm for finding minimum 3-way cuts in hypergraphs, which runs in O(dmn 3) time, where d is the sum of the degrees of all the vertices. We also give an O(n 4k--lg k) algorithm for finding all minimum k-way cuts in graphs. Our algorithm is based on a divide-and-conquer method and improves all well-known existing algorithms along this divide-and-conquer method. As for approximation algorithms, we determine the tight approximation ratio of a general greedy splitting algorithm (finding a minimum k-way cut by iteratively increasing a constant number of components). Our result implies that the approximation ratio of the algorithm that iteratively increases h -- 1 components is 2 -- h/k + O(h2 /k2), which settles a well-known open problem. / For an unweighted graph and a given subset T ⊂ V of k terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of l edges (respectively, non-terminal vertices), whose removal from G separates each terminal from all the others. We show that Edge Multiterminal Cut is polynomial-time solvable for 1 = O(log n) by presenting an O(2lkT(n, m)) algorithm, where T(n, m) is the running time of finding a maximum flow in unweighted graphs. We also give three algorithms for Vertex Multiterminal Cut that run in O(k lT(n, m)), O( l!2 2l T(n, m)) and O(lk 4lT( n, m)) time respectively. Furthermore, we obtain faster algorithms for small k: Edge 3-Terminal Cut can be solved in O(1.415lT(n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059 lT(n, m)), O(2.772 lT(n, m)), O(3.349 lT(n, m)) and O(3.857 lT(n, m)) times respectively. Our results on Multiterminal Cut can be used to obtain faster algorithms for Multicut. / In this thesis, we study algorithmic issues for three closely related partition problems in graphs: k-Way Cut (k-Cut), Multiterminal Cut, and Multicut. These three problems attempt to separate a graph, by edge or vertex deletion, into several components with certain properties. The k-Way Cut (k-Cut) problem is to separate the graph into k components, the Multiterminal Cut problem is to separate a subset of vertices away from each other, and the Multicut problem is to separate some given pairs of vertices. These three problems have many applications in parallel and distributed computing, VLSI system design, clustering problems, communications network and many others. / Xiao, Mingyu. / Adviser: Andrew C. Yao. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3617. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 85-92). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Thesis (M.Sc.)--York University, 2007. Graduate Programme in Computer Science and Engineering. / Typescript. Includes bibliographical references (leaves 170-173). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR38826

Thesis (M.Sc.)--York University, 2008. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 49-51). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR45954