Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 152-153).

No description available.

In this thesis, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. In such models, we are given an added time component and different capacity constraints for each time. Over time, capacities are weakly increasing as resources increase, allowing more items to be selected. Once an item is selected, it cannot be removed in future times. The goal is to maximize some (possibly also time-dependent) objective function under such packing constraints. In Chapter 2, we study the generalized incremental knapsack problem, a multi-period extension to the classical knapsack problem. We present a policy that reduces the generalized incremental knapsack problem to sequentially solving multiple classical knapsack problems, for which many efficient algorithms are known. We call such an algorithm a single-time algorithm. We prove that this algorithm gives a (0.17 - ⋲)-approximation for the generalized incremental knapsack problem. Moreover, we show that the algorithm is very efficient in practice. On randomly generated instances of the generalized incremental knapsack problem, it returns near optimal solutions and runs much faster compared to Gurobi solving the problem using the standard integer programming formulation. In Chapter 3, we present additional approximation algorithms for the generalized incremental knapsack problem. We first give a polynomial-time (½-⋲)-approximation, improving upon the approximation ratio given in Chapter 2. This result is based on a new reformulation of the generalized incremental knapsack problem as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Using the same sequencing reformulation, combined with further enumeration-based self-reinforcing ideas and new structural properties of nearly-optimal solutions, we give a quasi-polynomial time approximation scheme for the problem, thus ruling out the possibility that the generalized incremental knapsack problem is APX-hard under widely-believed complexity assumptions. In Chapter 4, we first turn our attention to the submodular monotone all-or-nothing incremental knapsack problem (IK-AoN), a special case of the submodular monotone function subject to a knapsack constraint extended to a multi-period setting. We show that each instance of IK-AoN can be reduced to a linear version of the problem. In particular, using a known PTAS for the linear version from literature as a subroutine, this implies that IK-AoN admits a PTAS. Next, we study special cases of the generalized incremental knapsack problem and provide improved approximation schemes for these special cases. In Chapter 5, we give a polynomial-time (¼-⋲)-approximation in expectation for the incremental generalized assignment problem, a multi-period extension of the generalized assignment problem. To develop this result, similar to the reformulation from Chapter 3, we reformulate the incremental generalized assignment problem as a multi-machine sequencing problem. Following the reformulation, we show that the (½-⋲)-approximation for the generalized incremental knapsack problem, combined with further randomized rounding techniques, can be leveraged to give a constant factor approximation in expectation for the incremental generalized assignment problem. In Chapter 6, we turn our attention to the incremental knapsack polytope. First, we extend one direction of Balas's characterization of 0/1-facets of the knapsack polytope to the incremental knapsack polytope. Starting from extended cover inequalities valid for the knapsack polytope, we show how to strengthen them to define facets for the incremental knapsack polytope. In particular, we prove that under the same conditions for which these inequalities define facets for the knapsack polytope, following our strengthening procedure, the resulting inequalities define facets for the incremental knapsack polytope. Then, as there are up to exponentially many such inequalities, we give separation algorithms for this class of inequalities.

An expected cost model was developed for failure detection in series systems under imperfect testing. Type I and type II error probabilities are included and single-pass sample paths are required. The model accounts for the expected costs of testing components, false positive termination, and no-defect-found outcomes. Based on the model, a heuristic was developed to construct the cost minimizing testing sequence. The heuristic algorithm utilizes elementary arithmetic computations and has been successfully applied to a variety of problems. Furthermore, the algorithm appears to be globally convergent. Choice of a starting solution affects the rate of convergence, and guidelines for selecting the starting solution were discussed. Implementation of the heuristic was illustrated by numerical example. / Master of Science

by Wai Ho Mow. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1993. / Includes bibliographical references (leaves 116-124). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Spread Spectrum Technique --- p.2 / Chapter 1.1.1 --- Pulse Compression Radars --- p.3 / Chapter 1.1.2 --- Spread Spectrum Multiple Access Systems --- p.6 / Chapter 1.2 --- Definitions and Notations --- p.8 / Chapter 1.3 --- Organization of this Thesis --- p.12 / Chapter 2 --- Lower Bounds on Correlation of Sequences --- p.15 / Chapter 2.1 --- Welch's Lower Bounds and Sarwate's Generalization --- p.16 / Chapter 2.2 --- A New Construction and Bounds on Odd Correlation --- p.23 / Chapter 2.3 --- Known Sequence Sets Touching the Correlation Bounds --- p.26 / Chapter 2.4 --- Remarks on Other Bounds --- p.27 / Chapter 3 --- Perfect Polyphase Sequences: A Unified Approach --- p.29 / Chapter 3.1 --- Generalized Bent Functions and Perfect Polyphase Sequences --- p.30 / Chapter 3.2 --- The General Construction of Chung and Kumar --- p.32 / Chapter 3.3 --- Classification of Known Constructions ...........； --- p.34 / Chapter 3.4 --- A Unified Construction --- p.39 / Chapter 3.5 --- Desired Properties of Sequences --- p.41 / Chapter 3.6 --- Proof of the Main Theorem --- p.45 / Chapter 3.7 --- Counting the Number of Perfect Polyphase Sequences --- p.49 / Chapter 3.8 --- Results of Exhaustive Searches --- p.53 / Chapter 3.9 --- A New Conjecture and Its Implications --- p.55 / Chapter 3.10 --- Sets of Perfect Polyphase Sequences --- p.58 / Chapter 4 --- Aperiodic Autocorrelation of Generalized P3/P4 Codes --- p.61 / Chapter 4.1 --- Some Famous Polyphase Pulse Compression Codes --- p.62 / Chapter 4.2 --- Generalized P3/P4 Codes --- p.65 / Chapter 4.3 --- Asymptotic Peak-to-Side-Peak Ratio --- p.66 / Chapter 4.4 --- Lower Bounds on Peak-to-Side-Peak Ratio --- p.67 / Chapter 4.5 --- Even-Odd Transformation and Phase Alphabet --- p.70 / Chapter 5 --- Upper Bounds on Partial Exponential Sums --- p.77 / Chapter 5.1 --- Gauss-like Exponential Sums --- p.77 / Chapter 5.1.1 --- Background --- p.79 / Chapter 5.1.2 --- Symmetry of gL(m) and hL(m) --- p.80 / Chapter 5.1.3 --- Characterization on the First Quarter of gL(m) --- p.83 / Chapter 5.1.4 --- Characterization on the First Quarter of hL(m) --- p.90 / Chapter 5.1.5 --- Bounds on the Diameters of GL(m) and HL(m) --- p.94 / Chapter 5.2 --- More General Exponential Sums --- p.98 / Chapter 5.2.1 --- A Result of van der Corput --- p.99 / Chapter 6 --- McEliece's Open Problem on Minimax Aperiodic Correlation --- p.102 / Chapter 6.1 --- Statement of the Problem --- p.102 / Chapter 6.2 --- A Set of Two Sequences --- p.105 / Chapter 6.3 --- A Set of K Sequences --- p.110 / Chapter 7 --- Conclusion --- p.113 / Bibliography --- p.124

Abstract not available

Partial exchangeability is the fundamental building block in the subjective approach to the probability of multi-type sequences which replaces the independence concept of the objective theory. The aim of this thesis is to present some theory for partially exchangeable sequences of random variables based on well-known results for exchangeable sequences. The reader is introduced to the concepts of partially exchangeable events, partially exchangeable sequences of random variables and partially exchangeable o-fields, followed by some properties of partially exchangeable sequences of random variables. Extending de Finetti's representation theorem for exchangeable random variables to hold for multi-type sequences, we obtain the following result to be used throughout the thesis: There exists a o-field, conditional upon which, an infinite partially exchangeable sequence of random variables behaves like an independent sequence of random variables, identically distributed within types. Posing (i) a stronger requirement (spherical symmetry) and (ii) a weaker requirement (the selection property) than partial exchangeability on the infinite multi-type sequence of random variables, we obtain results related to de Finetti's representation theorem for partially exchangeable sequences of random variables. Regarding partially exchangeable sequences as mixtures of independent and identically distributed (within types) sequences, we (i) give three possible expressions for the directed random measures of the partially exchangeable sequence and (ii) look at three possible expressions for the o-field mentioned in de Finetti's representation theorem. By manipulating random measures and using de Finetti's representation theorem, we point out some concrete ways of constructing partially exchangeable sequences. The main result of this thesis follows by extending de Finetti's represen. tation theorem in conjunction with the Chatterji principle to obtain the following result: Given any a.s. limit theorem for multi-type sequences of independent random variables, identically distributed within types, there exists an analogous theorem satisfied by all partially exchangeable sequences and by all sub-subsequences of some subsequence of an arbitrary dependent infinite multi-type sequence of random variables, tightly distributed within types. We finally give some limit theorems for partially exchangeable sequences of random variables, some of which follow from the above mentioned result. / Thesis (Ph.D.)-University of Natal, Durban, 1991.

Thesis (Ph. D.)--University of Oregon, 2008. / Typescript. Includes vita and abstract. Includes bibliographical references (leaves 71-72). Also available online in Scholars' Bank; and in ProQuest, free to University of Oregon users.

Orientador: Miguel Natálio Abadi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T15:39:00Z (GMT). No. of bitstreams: 1 Lambert_Rodrigo_M.pdf: 3549677 bytes, checksum: 663438e1feb8f7092723382b6846bc9c (MD5) Previous issue date: 2010 / Resumo: Seja x um alfabeto finito ou enumerável, e considere o espaço de todas as sequências finitas compostas por concatenação de símbolos desse alfabeto. A essas sequências daremos o nome de palavras. Denotaremos por xn conjunto de todas as palavras de tamanho n. No presente trabalho, consideramos uma função que leva cada palavra de tamanho n em um número inteiro entre 0 e n - 1. Essa função é definida pelo maior tamanho possível de uma sobreposição da palavra com uma cópia dela mesma transladada, e é chamada de função de sobreposição. A ela daremos o nome de Sn. A relevância da função de sobreposição foi colocada em evidência, entre outros casos, na análise estatística da Recorrência de Poincaré, e possui relação explícita com a entropia do processo. Nesse trabalho, provamos a convergência da distribuição da função de sobreposição, quando a sequência _e escolhida de acordo com relação a n variáveis aleatórias independentes e identicamente distribuídas no alfabeto x. Também apresentamos um limitante para a velocidade dessa convergência. Como consequência, mostramos também a convergência da esperança e da variância da função de sobreposição. / Abstract: We consider the set of finite sequencies of length n over a finite or contable alphabet x. We consider the function defined over xn which gives the size of the maximum overlap of a given sequence with a (shifted) copy of itself. That function will be denoted by overlapping function. We prove the convergence of the distribution of this function when the sequence is chosen according to a product measure, with identically distributed marginals. We give a point-wise upper bound for the velocity of this convergence. As a byproduct, we show the convergence of te mean and the variance of the overlapping function. / Mestrado / Probabilidade / Mestre em Estatística

We study weak convergence of sequences in Banach spaces. In particular, we compare the notions of weak and norm convergence. Although these modes of convergence usually differ, we show that in ℓ¹ they coincide. We then show a theorem of Rosenthal's which states that if {𝓍ₙ} is a bounded sequence in a Banach space, then {𝓍ₙ} has a subsequence {𝓍'ₙ} satisfying one of the following two mutually exclusive alternatives; (i) {𝓍'ₙ} is weakly Cauchy, or (ii) {𝓍'ₙ} is equivalent to the unit vector basis of ℓ¹.