Thesis (M.S.)--Oregon State University, 1993. / Typescript (photocopy). Includes bibliographical references (leaves 48-49). Also available on the World Wide Web.

Thesis (Ph. D.)--Drexel University, 2006. / Includes abstract and vita. Includes bibliographical references (leaves 92-97).

Multi-homing is a technology used by Internet Service Provider (ISP) to connect to the Internet via multiple networks. This connectivity enhances the network reliability and service quality of the ISP. However, using multi-networks may imply multiple costs on the ISP. To make full use of the underlying networks with minimum cost, a routing strategy is requested by ISPs. Of course, this optimal routing strategy depends on the pricing regime used by network providers. In this study we investigate a relatively new pricing regime – top-percentile pricing. Under top-percentile pricing, network providers divide the charging period into several fixed length time intervals and calculate their cost according to the traffic volume that has been shipped during the θ-th highest time interval. Unlike traditional pricing regimes, the network design under top-percentile pricing has not been fully studied. This paper investigates the optimal routing strategy in case where network providers charge ISPs according to top-percentile pricing. We call this problem the Top-percentile Traffic Routing Problem (TpTRP). As the ISP cannot predict next time interval’s traffic volume in real world application, in our setting up the TpTRP is a multi-stage stochastic optimisation problem. Routing decisions should be made at the beginning of every time period before knowing the amount of traffic that is to be sent. The stochastic nature of the TpTRP forms the critical difficulty of this study. In this paper several approaches are investigated in either the modelling or solving steps of the problem. We begin by exploring several simplifications of the original TpTRP to get an insight of the features of the problem. Some of these allow analytical solutions which lead to bounds on the achievable optimal solution. We also establish bounds by investigating several “naive” routing policies. In the second part of this work, we build the multi-stage stochastic programming model of the TpTRP, which is hard to solve due to the integer variables introduced in the calculation of the top-percentile traffic. A lift-and-project based cutting plane method is investigated in solving the SMIP for very small examples of TpTRP. Nevertheless it is too inefficient to be applicable on large sized instances. As an alternative, we explore the solution of the TpTRP as a Stochastic Dynamic Programming (SDP) problem by a discretization of the state space. This SDP model gives us achievable routing policies on small size instances of the TpTRP, which of course improve the naive routing policies. However, the solution approach based on SDP suffers from the curse of dimensionality which restricts its applicability. To overcome this we suggest using Approximate Dynamic Programming (ADP) which largely avoids the curse of dimensionality by exploiting the structure of the problem to construct parameterized approximations of the value function in SDP and train the model iteratively to get a converged set of parameters. The resulting ADP model with discrete parameter for every time interval works well for medium size instances of TpTRP, though it still requires too long to be trained for large size instances. To make the realistically sized TpTRP problem solvable, we improve on the ADP model by using Bezier Curves/Surfaces to do the aggregation over time. This modification accelerates the efficiency of parameter training in the solution of the ADP model, which makes the realistically sized TpTRP tractable.

The internet has facilitated music metadata production and distribution on an unprecedented scale. A contributing factor of this data deluge is a change in the authorship of this data from the expert few to the untrained crowd. The resulting unordered flood of imperfect annotations provides challenges and opportunities in identifying accurate metadata and linking it to the music audio in order to provide a richer listening experience. We advocate novel adaptations of Dynamic Programming for music metadata synchronisation, ranking and comparison. This thesis introduces Windowed Time Warping, Greedy, Constrained On-Line Time Warping for synchronisation and the Concurrence Factor for automatically ranking metadata. We begin by examining the availability of various music metadata on the web. We then review Dynamic Programming methods for aligning and comparing two source sequences whilst presenting novel, specialised adaptations for efficient, realtime synchronisation of music and metadata that make improvements in speed and accuracy over existing algorithms. The Concurrence Factor, which measures the degree in which an annotation of a song agrees with its peers, is proposed in order to utilise the wisdom of the crowds to establish a ranking system. This attribute uses a combination of the standard Dynamic Programming methods Levenshtein Edit Distance, Dynamic Time Warping, and Longest Common Subsequence to compare annotations. We present a synchronisation application for applying the aforementioned methods as well as a tablature-parsing application for mining and analysing guitar tablatures from the web. We evaluate the Concurrence Factor as a ranking system on a largescale collection of guitar tablatures and lyrics to show a correlation with accuracy that is superior to existing methods currently used in internet search engines, which are based on popularity and human ratings.

No description available.

Wang, Chongyu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 74-78). / Abstract also in Chinese. / Abstract --- p.1 / Abstract in Chinese --- p.3 / Acknowledgement --- p.4 / Contents --- p.5 / List of Tables --- p.7 / List of Figures --- p.8 / Chapter 1. --- Introduction --- p.9 / Chapter 2. --- Conventional Dynamic Programming --- p.15 / Chapter 2.1. --- Principle of optimality and decomposition --- p.15 / Chapter 2.2. --- Backward dynamic programming --- p.17 / Chapter 2.3. --- Forward dynamic programming --- p.20 / Chapter 2.4. --- Curse of dimensionality --- p.23 / Chapter 3. --- Surrogate Constraint Formulation --- p.26 / Chapter 3.1. --- Surrogate constraint formulation --- p.26 / Chapter 3.2. --- Singly constrained dynamic programming --- p.28 / Chapter 3.3. --- Surrogate dual search --- p.29 / Chapter 4. --- Distance Confined Path Algorithm --- p.34 / Chapter 4.1. --- Yen´ةs algorithm for the kth shortest path problem --- p.35 / Chapter 4.2. --- Application of Yen´ةs method to integer programming --- p.36 / Chapter 4.3. --- Distance confined path problem --- p.42 / Chapter 4.4. --- Application of distance confined path formulation to integer programming --- p.50 / Chapter 5. --- Convergent Surrogate Dual Search --- p.59 / Chapter 5.1. --- Algorithm for convergent surrogate dual search --- p.62 / Chapter 5.2. --- "Solution schemes for (Pμ{αk,αβ)) and f(x) = αk" --- p.63 / Chapter 5.3. --- Computational Results and Analysis --- p.68 / Chapter 6. --- Conclusions --- p.72 / Bibliography --- p.74

<p>The power to mass ratio of a heavy truck causes even moderate slopes to have a significant influence on the motion. The velocity will inevitable vary within an interval that is primarily determined by the ratio and the road topography. If further variations are actuated by a controller, there is a potential to lower the fuel consumption by taking the upcoming topography into account. This possibility is explored through theoretical and simulation studies as well as experiments in this work.</p><p>Look-ahead control is a predictive strategy that repeatedly solves an optimization problem online by means of a tailored dynamic programming algorithm. The scenario in this work is a drive mission for a heavy diesel truck where the route is known. It is assumed that there is road data on-board and that the current heading is known. A look-ahead controller is then developed to minimize fuel consumption and trip time.</p><p>The look-ahead control is realized and evaluated in a demonstrator vehicle and further studied in simulations. In the prototype demonstration, information about the road slope ahead is extracted from an on-board database in combination with a GPS unit. The algorithm calculates the optimal velocity trajectory online and feeds the conventional cruise controller with new set points. The results from the experiments and simulations confirm that look-ahead control reduces the fuel consumption without increasing the travel time. Also, the number of gear shifts is reduced. Drivers and passengers that have participated in tests and demonstrations have perceived the vehicle behavior as comfortable and natural.</p> / Report code: LIU-TEK-LIC-2007:28.

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(lambda) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(lambda) and Q-learning belong.

The goals of gene prediction using computational approaches are to determine gene location and the corresponding functionality of the coding region. A subset of gene prediction is the gene structure prediction problem, which is to define the exon-intron boundaries of a gene. Gene prediction follows two general approaches: statistical patterns identification and sequence similarity comparison. Similarity based approaches have gained increasing popularity with the recent vast increase in genomic data in GenBank. The proposed gene prediction algorithm is a similarity based algorithm which capitalizes on the fact that similar sequences bear similar functions. The proposed algorithm, like most other similarity based algorithms, is based on dynamic programming. Given a genomic DNA, X = x1 xn and a closely related cDNA, Y = y1 yn, these sequences are aligned with matching pairs stored in a data set. These indexes of matching sets contain a large jumble of all matching pairs, with a lot of cross over indexes. Dynamic programming alignment is again used to retrieve the longest common non-crossing subsequence from the collection of matching fragments in the data set. This algorithm was implemented in Java on the Unix platform. Statistical comparisons were made against other software programs in the field. Statistical evaluation at both the DNA and exonic level were made against Est2genome, Sim4, Spidey, and Fgenesh-C. The proposed gene structure prediction algorithm, by far, has the best performance in the specificity category. The resulting specificity was greater than 98%. The proposed algorithm also has on par results in terms of sensitivity and correlation coeffcient. The goal of developing an algorithm to predict exonic regions with a very high level of correctness was achieved.

This thesis considers a variant of the classical problem for finding the longest common subsequence (LCS) called longest common subsequence problem with a gapped constraint (LCSGC). Given two sequences A, B, and a constrained sequence C, which is accomplished with a corresponding gapped constraint for each symbol, whose lengths are m, n, and r, respectively, the LCSGC problem is to find an LCS of A and B, such that C is also a subsequence of this LCS and the gapped constraints corresponding to C are satisfied. In this thesis, two algorithms with time complexities O(m2n2r) and O(mnr ¡Ñ min(m, n)) are proposed based on the dynamic programming technique for solving the LCSGC problem.