published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

published_or_final_version / Mathematics / Master / Master of Philosophy

In the past few years, there has been a strong and growing interest in evaluating the expected behavior of what we call combinatorial bin packing problems. A combinatorial bin packing problem consists of a number of items of various sizes and value ratios (value per unit of size) along with a collection of bins of fixed capacity into which the items are to be packed. The packing must be done in such a way that the sum of the sizes of the items into a given bin does not exceed the capacity of that bin. Moreover, an item must either be packed into a bin in its entirety or not at all: this "all or nothing" requirement is why these problems are characterized as being combinatorial. The objective of the packing is to optimize a given criterion Junction. Here optimize means either maximize or minimize, depending on the problem. We study two problems that fit into this framework: the Knapsack Problem and the Minimum Sum of Squares Problem. Both of these problems are known to be in the class of NP-hard problems and there is ample reason to suspect that these problems do not admit of efficient exact solution. We obtain results concerning the performance of heuristics under the assumption that the inputs are random samples from some distribution. For the Knapsack Problem, we develop four heuristics, two of which are on-line and two off-line. All four heuristics are shown to be asymptotically optimal in expectation when the item sizes and value ratios are assumed to be independent and uniform. One heuristic is shown to be asymptotically optimal in expectation when the item sizes are uniformly distributed and the value ratios are exponentially distributed. The amount of time required by these heuristics is no more than proportional to the amount of time required to sort the items in order of nonincreasing value ratios. For the Minimum Sum of Squares Problem, we develop two heuristics, both of which are off-line. Both of these heuristics are shown to be asymptotically optimal in expectation when the sizes of the items input are assumed uniformly distributed.

No description available.

Approved for public release; distribution is unlimited / Surgical technicians at Naval hospitals provide a host of services related to surgical procedures that include handing instruments to surgeons, assisting operating room nurses, prepping and cleaning operating rooms, and administrative duties. At the Naval Medical Center San Diego (NMCSD), there are 83 surgical technicians that must be scheduled for these duties. The three military and one civilian hospital interviewed for this thesis manually schedule these duties. Weaknesses of these manual schedules exposed during interviews at these hospitals include assignment inequities and the time needed to create them. This thesis reports on an optimization based and spreadsheet implemented tool developed to schedule surgical technicians for both daily and weekly duties at a Naval hospital. We demonstrate the tool for the surgical technician department at NMCSD. The schedulers at NMCSD verify the utility of the developed tool and cite a drastic reduction in the time required to generate timely, equitable, and accurate schedules. The study also investigates historical operating room usage data and makes suggestions for improving scheduling practices based on these data. / Commander (Select), United States Navy

Gives the basic definitions and theorems of similar partially ordered sets; studies finite partially ordered sets, including the problem of combinatorial analysis; and includes the ideas of complete, dense, and continuous partially ordered sets, including proofs.

An MSc dissertation by Shivani Singh. University of Witwatersrand Faculty of Science, School of Mathematics. August 2016. / These symmetries have interesting applications to enumerative combinatorics and to Ramsey theory. The aim of this thesis will be to present some important results in these fields. In particular, we shall enumerate the r-ary symmetric bracelets of length n. / LG2017

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2017. / In this thesis, various partition functions with respect to `-regular overpartitions, a special partition inequality and partition con gurations are studied. We explore new combinatorial properties of overpartitions which are natural generalizations of integer partitions. Building on recent work, we state general combinatorial identities between standard partition, overpartition and `-regular partition functions. We provide both generating function and bijective proofs. We then establish an in nite set of Ramanujan-type congruences for the `-regular overpartitions. This signi cantly extends the recent work of Shen which focused solely on 3{regular overpartitions and 4{regular overpartitions. We also prove some of the congruences for `-regular overpartition functions combinatorially. We then provide a combinatorial proof of the inequality p(a)p(b) > p(a+b), where p(n) is the partition function and a; b are positive integers satisfying a+b > 9, a > 1 and b > 1. This problem was posed by Bessenrodt and Ono who used the inequality to study a maximal multiplicative property of an extended partition function. Finally, we consider partition con gurations introduced recently by Andrews and Deutsch in connection with the Stanley-Elder theorems. Using a variation of Stanley's original technique, we give a combinatorial proof of the equality of the number of times an integer k appears in all partitions and the number of partition con- gurations of length k. Then we establish new generalizations of the Elder and con guration theorems. We also consider a related result asserting the equality of the number of 2k's in partitions and the number of unrepeated multiples of k, providing a new proof and a generalization. / MT2017

The mathematical theory of nding a basis of shortest possible vectors in a given lattice L is known as reduction theory and goes back to the work of Lagrange, Gauss, Hermite, Korkin, Zolotarev, and Minkowski. Modern reduction theory is voluminous and includes the work of A. Lenstra, H. Lenstra and L. Lovasz who created the well known LLL algorithm, and many other researchers such as L. Babai and C. P. Schnorr who created signi cant new variants of basis reduction algorithms. The shortest vector (SVP) and closest vector (CVP) problems, presently considered intractable, are algorithmic tasks that lie at the core of many number theoretic problems, integer programming, nding irreducible factors of polynomials, minimal polynomials of algebraic numbers, and simultaneous diophantine approximation. Lattice basis reduction also has deep and extensive connections with modern cryptography, and cryptanalysis particularly in the post-quantum era. In this dissertation we study and compare current systems LLL and BKZ, and point out their strengths and drawbacks. In addition, we propose and investigate the e cacy of new optimization techniques, to be used along with LLL, such as hill climbing, random walks in groups, our lattice di usion-sub lattice fusion, and multistage hybrid LDSF-HC technique. The rst two methods rely on the sensitivity of LLL to permutations of the input basis B, and optimization ideas over the symmetric group Sm viewed as a metric space. The third technique relies on partitioning the lattice into sublattices, performing basis reduction in the partition sublattice blocks, fusing the sublattices, and repeating. We also point out places where parallel computation can reduce runtimes achieving almost linear speedup. The multistage hybrid technique relies on the lattice di usion and sublattice fusion and hill climbing algorithms. Unlike traditional methods, our approach brings in better results in terms of basis reduction towards nding shortest vectors and minimal weight bases. Using these techniques we have published the competitive lattice vectors of ideal lattice challenge on the lattice hall of fame. Toward the end of the dissertation we also discuss applications to the multidimensional knapsack problem that resulted in the discovery of new large sets of geometric designs still considered very rare. The research introduces innovative techniques in lattice basis reduction theory and provides some space for future researchers to contemplate lattices from a new viewpoint. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2016. / FAU Electronic Theses and Dissertations Collection