Tong Kwong-Bun. / Thesis submitted in: December 2002. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 77-[80]). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- An Overview --- p.1 / Chapter 1.2 --- Tree Search --- p.2 / Chapter 1.2.1 --- Minimax Algorithm --- p.2 / Chapter 1.2.2 --- The Alpha-Beta Algorithm --- p.4 / Chapter 1.2.3 --- Alpha-Beta Enhancements --- p.5 / Chapter 1.2.4 --- Selective Search --- p.9 / Chapter 1.3 --- Construction of Evaluation Function --- p.16 / Chapter 1.4 --- Contribution of the Thesis --- p.17 / Chapter 1.5 --- Structure of the Thesis --- p.19 / Chapter 2 --- The Probabilistic Forward Pruning Framework --- p.20 / Chapter 2.1 --- Introduction --- p.20 / Chapter 2.2 --- The Generalized Probabilistic Forward Cuts Heuristic --- p.21 / Chapter 2.3 --- The GPC Framework --- p.24 / Chapter 2.3.1 --- The Alpha-Beta Algorithm --- p.24 / Chapter 2.3.2 --- The NegaScout Algorithm --- p.25 / Chapter 2.3.3 --- The Memory-enhanced Test Algorithm --- p.27 / Chapter 2.4 --- Summary --- p.27 / Chapter 3 --- The Fast Probabilistic Forward Pruning Framework --- p.30 / Chapter 3.1 --- Introduction --- p.30 / Chapter 3.2 --- The Fast GPC Heuristic --- p.30 / Chapter 3.2.1 --- The Alpha-Beta algorithm --- p.32 / Chapter 3.2.2 --- The NegaScout algorithm --- p.32 / Chapter 3.2.3 --- The Memory-enhanced Test algorithm --- p.35 / Chapter 3.3 --- Performance Evaluation --- p.35 / Chapter 3.3.1 --- Determination of the Parameters --- p.35 / Chapter 3.3.2 --- Result of Experiments --- p.38 / Chapter 3.4 --- Summary --- p.42 / Chapter 4 --- The Node-Cutting Heuristic --- p.43 / Chapter 4.1 --- Introduction --- p.43 / Chapter 4.2 --- Move Ordering --- p.43 / Chapter 4.2.1 --- Quality of Move Ordering --- p.44 / Chapter 4.3 --- Node-Cutting Heuristic --- p.46 / Chapter 4.4 --- Performance Evaluation --- p.48 / Chapter 4.4.1 --- Determination of the Parameters --- p.48 / Chapter 4.4.2 --- Result of Experiments --- p.50 / Chapter 4.5 --- Summary --- p.55 / Chapter 5 --- The Integrated Strategy --- p.56 / Chapter 5.1 --- Introduction --- p.56 / Chapter 5.2 --- "Combination of GPC, FGPC and Node-Cutting Heuristic" --- p.56 / Chapter 5.3 --- Performance Evaluation --- p.58 / Chapter 5.4 --- Summary --- p.63 / Chapter 6 --- Conclusions and Future Works --- p.64 / Chapter 6.1 --- Conclusions --- p.64 / Chapter 6.2 --- Future Works --- p.65 / Chapter A --- Examples --- p.67 / Chapter B --- The Rules of Chinese Checkers --- p.73 / Chapter C --- Application to Chinese Checkers --- p.75 / Bibliography --- p.77

Abstract not available

Graduation date: 2004

Biologists need tools to see the structural relationships encoded in biological sequences (strings). The Walking Tree heuristics calculate some of these relationships. I have designed and implemented graphic presentations which allow the biologist (user) to see these relations. This thesis contains background information on the biological sequences and some background on the Walking Tree heuristics. I demonstrate my methods by showing a visual matching of mitochondrial genomes. I also show matchings based on amino acids and on hydrophobicity. I also show how the parameters of the visualization can be varied to produce more useful pictures. I implemented a parallel version of the Walking Tree heuristic and used it to produce a phylogenetic tree for picornaviruses. I also implemented several user interfaces. These programs are available on my WWW page which allows a user to produce a picture of a matching by giving the sequences in Gen Bank format and by making a few mouse clicks. / Graduation date: 1998

This dissertation focuses on improvements in vehicle routing that can be gained by allowing multiple vehicles to service a common load. We explore how costs can be reduced through the elimination of the constraint that a load must be serviced by only one vehicle. Specifically, we look at the problem of routing vehicles to service loads that have distinct origins and destinations, with no constraint on the amount of a load that a vehicle may service. We call this the Pickup and Delivery Problem with Split Loads (PDPSL). We model this problem as a dynamic program and introduce structural results that can help practitioners implement the use of split loads, including the definition of an upper bound on the benefit of split loads. This bound indicates that the routing cost can be reduced by at most one half when split loads are allowed. Furthermore, the most benefit occurs when load sizes are just above one half of vehicle capacity. We develop a heuristic for the solution of large scale problems, and apply this heuristic to randomly generated data sets. Various load sizes are tested, with the experimental results supporting the finding that most benefit with split loads occurs for load sizes just above one half vehicle capacity. Also, the average benefit of split loads is found to range from 6 to 7% for most data sets. The heuristic was also tested on a real world example from the trucking industry. These tests reveal the benefit of both using split loads and allowing fleet sharing. The benefit for split loads is not as significant as with the random data, and the various business rules added for this case are tested to find those that have the most impact. It is found that an additional cost for every stop the vehicle makes strictly limits the potential for benefit from split loads. Finally, we present a simplified version of the PDPSL in which all origins are visited prior to any destination on a route, generalizing structural results from the Split Delivery Vehicle Routing Problem for this problem.

People are increasingly concerned about online privacy and how computers collect, process, share, and store their personal information. Such concerns are understandable given the growing number of privacy invasions and the pervasiveness of information capture and sharing between IT systems. This situation has led to an increasingly regulated environment, limiting what systems may do, and what safeguards they must offer users. Privacy is an especially important concern in the fields of computer supported collaborative work (CSCW), Ubiquitous Computing, and e-commerce, where the nature of the applications often requires some information collection and sharing. In order to minimize risks to users it is essential to identify privacy problems early in the design process. Several methods and frameworks for accomplishing this have been proposed in the last decades. These frameworks, though based on hard-earned experience and great insight, have not seen widespread adoption despite the high level of interest in this topic. Part of the reason for this is likely the lack of evaluation and study of these frameworks. In our research we examine the key design and analysis frameworks and their elements, and compare these to the kinds of problems users face and are concerned with in terms of privacy. Based on this analysis of the relative strengths and weaknesses of existing design frameworks we derive a new design framework; STRAP (STRuctured Analysis of Privacy). In STRAP we combine light-weight goal-oriented analysis with heuristics to provide a simple yet effective design framework. We validate our analysis by demonstrating in a series of design experiments that STRAP is more efficient and effective than any one of the existing design frameworks, and provide quantitative and qualitative evidence of the value of using such frameworks as part of the design process.

Bin packing is a problem with many applications in various industries. This thesis addresses a specific instance of the this problem, known as the Container Packing problem. Special attention is paid to the Pallet Loading problem which is a restricted sub-problem of the general Container Packing problem. Since the Bin Packing problem is NP-complete, it is customary to apply a heuristic measure in order to approximate solutions in a reasonable amount of computation time rather than to attempt to produce optimal results by applying some exact algorithm. Several heuristics are examined for the problems under consideration, and the results produced by each are shown and compared where relevant. / Thesis (M.Sc.)-University of Natal, Durban, 1991.

Thesis (M.S.) -- Mississippi State University. Department of Computer Science and Engineering. / Title from title screen. Includes bibliographical references.

Thesis (Dr. rer. nat.)--Technische Universität München, 2000. / "Infix"--Cover. Includes bibliographical references (p. [164]-175) and index.

Thesis (M.S.)--West Virginia University, 2004. / Title from document title page. Document formatted into pages; contains x, 143 p. : ill. (some col.), maps (some col.). Includes abstract. Includes bibliographical references (p. 86-94).