We say that a covering space of the surface S over X has the Birman--Hilden property if the subgroup of the mapping class group of X consisting of mapping classes that have representatives that lift to S embeds in the mapping class group of S modulo the group of deck transformations. We identify one necessary condition and one sufficient condition for when a covering space has this property. We give new explicit examples of irregular branched covering spaces that do not satisfy the necessary condition as well as explicit covering spaces that satisfy the sufficient condition. Our criteria are conditions on simple closed curves, and our proofs use the combinatorial topology of curves on surfaces.

A k × n array with entries from a q-letter alphabet is called a t-covering array if each t × n submatrix contains amongst its columns each one of the gt different words of length t that can be produced by the q letters. In the present article we use a probabilistic approach based on an appropriate Markov chain embedding technique, to study a t-covering problem where, instead of looking at all possible t ×n submatrices, we consider only submatrices of dimension t ×n with its rows being consecutive rows of the original k × n array. Moreover, an exact formula is established for the probability distribution function of the random variable, which enumerates the number of deficient submatrices (i.e., submatrices with at least one missing word, amongst their columns), in the case of a k × n binary matrix (q = 2) obtained by realizing kn Bernoulli variables.

Interval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms. Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm. Demand-covering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm. K-pack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.

Thesis (MCom)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Kohler Signs (PTY) Ltd is a sign production company located in Cape Town, South Africa. They manufacture and install signs for the City of Cape Town and private companies as well as manufacture advertisement signs to be placed on vehicles. Road signs consist of steel sheets that are cut and bent to the appropriate size and frame, and an image design, which is cut from re ective vinyl, are applied to the bent steel sheet. The image design consists of various letters, numbers and symbols which are categorised as irregular items. When these irregular items are combined in a distinctive way, with the use of di erent coloured vinyl, they convey a message to the road user which may be to yield for pedestrians crossing the street, or indicate to the road user the various highway exits that exist on the interchange ahead. These irregular items are placed upon re ective vinyl for cutting which results in vinyl o cuts that are wasted. The focus of this thesis is to minimise the waste incurred by placing these irregular items upon the vinyl in an optimal and timely manner for industry use. The vinyl printer, which cuts the irregular items out of the vinyl, consists of a xed width and is only limited in height by the vinyl itself. Thus, this problem may be described as a Two Dimensional Irregular Strip Packing Problem. These irregular items have only a few possible heights for each type of irregular item packed, which allows these irregular items to be packed as a level packing problem. The items are packed within levels as though they are regular items with the assistance of a prede ned rule-set. In this thesis various packing algorithms and image processing methodologies from the literature are researched and used to develop a new packing algorithm for this speci c problem. The newly developed algorithm is put through various benchmarks to test its performance. Some of these benchmarks are procured from Kohler Signs themselves, whereas others are randomly generated under certain conditions. These benchmarks reveal that the newly developed algorithm performs better for both the minimisation of waste and the minimisation of algorithm running time than the tried and trusted techniques utilised in industry by Kohler Signs. / AFRIKAANSE OPSOMMING: Kohler Signs (EDMS) Bpk is 'n padteken produksie maatskappy gele e in Kaapstad, Suid-Afrika. Hulle vervaardig en installeer tekens vir die Stad van Kaapstad en privaat maatskappye, sowel as advertensietekens wat op voertuie geplaas word. Padtekens bestaan uit staalplate wat gesny en gebuig word tot die toepaslike grootte en vorm. 'n Beeldontwerp, wat gesny is uit re ektiewe viniel, word vasgesit op die gebuigde staalplaat. Die beeldontwerp bestaan uit verskeie letters, getalle en simbole wat geklassi seer word as onre elmatige items. Wanneer hierdie onre elmatige items gekombineer word op 'n eiesoortige manier, met die gebruik van verskillende kleure viniel, dra hulle 'n boodskap oor aan die padgebruiker, soos byvoorbeeld om toe te gee aan voetgangers by 'n voetoorgang of dit dui aan die padgebruiker die verskillende snelweguitgange wat bestaan op die wisselaar wat voorl^e. Hierdie onre elmatige items word op re ektiewe viniel geplaas en uitgesny wat lei tot die vermorsing van stukkies viniel. Die fokus van hierdie tesis is om die onre elmatige items op 'n optimale en tydige wyse vir gebruik in industrie, op die viniel te plaas sodat die afval stukkies viniel geminimeer word. Die vinieldrukker, wat die onre elmatige items sny uit die viniel, bestaan uit 'n vaste wydte en is slegs beperk in hoogte deur die viniel self. Dus kan hierdie probleem beskryf word as 'n Twee-Dimensionele Onre elmatige Strookverpakkingsprobleem. Hierdie onre elmatige items het slegs 'n paar moontlike hoogtes vir elke tipe van onre elmatige item wat verpak word, wat dit moontlik maak om hierdie onre elmatige items te verpak as 'n strook verpakkingsprobleem. Die items word met behulp van 'n gede nieerde stel re els binne vlakke verpak asof hulle re elmatige items is. In hierdie tesis is verskeie verpakkingsalgoritmes en beeldverwerkingsmetodes van die literatuur nagevors en gebruik om 'n nuwe verpakkingsalgoritme vir hierdie spesi eke probleem te ontwikkel. Die nuut ontwikkelde algoritme se prestasie is deur middel van verskeie normbepalingsvoorbeelde getoets. Sommige van hierdie normbepalingsvoorbeelde is verkry van Kohler Signs self, terwyl ander lukraak gegenereer is onder sekere voorwaardes. Hierdie normbepalingsvoorbeelde toon dat die nuut ontwikkelde algoritme beter vaar as die beproefde tegnieke gebruik in industrie deur Kohler Signs vir beide die minimering van vermorsde viniel sowel as die minimering van die algoritme se uitvoertyd.

People rely on the ability to transmit information over channels of communication that aresubject to noise and interference. This makes the ability to detect and recover from errorsextremely important. Coding theory addresses this need for reliability. A fundamentalquestion of coding theory is whether and how we can correct the errors in a message thathas been subjected to interference. One answer comes from structures known as errorcorrecting codes.A well studied parameter associated with a code is its covering radius. The coveringradius of a code is the smallest radius such that every vector in the Hamming space of thecode is contained in a ball of that radius centered around some codeword. Covering radiusrelates to an important decoding strategy known as nearest neighbor decoding.The multicovering radius is a generalization of the covering radius that was proposed byKlapper [11] in the course of studying stream ciphers. In this work we develop techniques forfinding the multicovering radius of specific codes. In particular, we study the even weightcode, the 2-error correcting BCH code, and linear codes with covering radius one.We also study questions involving the complexity of finding the multicovering radius ofcodes. We show: Lower bounding the m-covering radius of an arbitrary binary code is NPcompletewhen m is polynomial in the length of the code. Lower bounding the m-coveringradius of a linear code is Σp2-complete when m is polynomial in the length of the code. IfP is not equal to NP, then the m-covering radius of an arbitrary binary code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time. Note that the case when m = 1 was also previouslyunknown. If NP is not equal to Σp2, then the m-covering radius of a linear code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time.

Graduation date: 1998

We apply branched covering techniques to construct minimal simply-connected symplectic 4-manifolds with small χ_h values. We also use these constructions to provide an alternate proof that for each s ≥ 0, there exists a positive integer λ(s) such that each pair (j,8j+s) with j ≥ λ(s) is realized as (χ_h(M),c_1^2(M)) for some minimal simply-connected symplectic M. The smallest values of λ(s) currently known to the author are also explicitly computed for 0 ≤ s ≤ 99. Our computations in these cases populate 19 952 points in the (χ,c)-plane not previously realized in the existing literature.

We apply branched covering techniques to construct minimal simply-connected symplectic 4-manifolds with small χ_h values. We also use these constructions to provide an alternate proof that for each s ≥ 0, there exists a positive integer λ(s) such that each pair (j,8j+s) with j ≥ λ(s) is realized as (χ_h(M),c_1^2(M)) for some minimal simply-connected symplectic M. The smallest values of λ(s) currently known to the author are also explicitly computed for 0 ≤ s ≤ 99. Our computations in these cases populate 19 952 points in the (χ,c)-plane not previously realized in the existing literature.

We address a number of operational challenges encountered in two emerging types of practices in the procurement of truckload transportation services: collaboration and auctions. The main objective in these two types of procurement strategies is identifying and exploiting synergies between the lanes of a carrier's network. In shipper collaboration, we take the perspective of a shipper who collaborates with other shippers to seek synergy between his lanes and other participants' lanes. On the other hand, in procurement auctions, although we take the carriers' perspective in our work, a shipper tries to discover the carrier (or carriers) whose network has the most synergy with his lanes. The first part of the thesis concerns the solution of optimization problems arising in collaborative transportation procurement networks where a group of shippers comes together and jointly negotiates with carriers for the procurement of transportation services. Through collaboration, shippers may be able to identify and submit sequences of continuous loaded movements to carriers, reducing the carriers' need for repositioning, and thus lowering the carriers' costs. A portion of the carriers' cost savings may be returned to the shippers in the form of lower prices. We discuss optimization technology that helps identify repeatable, dedicated truckload continuous move tours with little truck repositioning. Timing considerations are critical to practical viability and are a key focus of our efforts. We demonstrate the effectiveness of our algorithms on randomly generated instances as well as on instances derived from real-world data. The second part concerns the pricing of transportation services offered by the trucking companies (carriers). We look at the bid determination problem faced by carriers in transportation procurement auctions where a shipper requests quotes from multiple carriers and purchases the services of the lowest bidder. The specific problem being studied is the bid valuation problem in the case where the carrier must place bids on multiple lanes simultaneously. We model the problem as a stochastic optimization problem and propose a coordinate search algorithm for solving this problem. Then, we conduct a simulation study to demonstrate the positive impact of the approach on carrier profits.

In this thesis, we introduce a new class of problems, which we call Optimal Areal Positioning (OAP), and study a special form of these problems. OAPs have important applications in earth observation satellite management, tele-robotics, multi-camera control, and surveillance. In OAP, we would like to find the optimal position of a set of floating geometric objects (targets) on a two-dimensional plane to (partially) cover another set of fixed geometric objects (requests) in order to maximize the total reward obtained from covered parts of requests. In this thesis, we consider the special form of OAP in which targets and requests are parallel axes rectangles and targets are of equal size. A predetermined reward is associated with covering an area unit of each request. Based on the number of target rectangles, we classify rectangular OAP into two categories: Single Target Problem (STP) and Multi-Target Problem (MTP). The structure of MTP can be compared to the planar p-center which is NP-complete, if p is part of the input. In fact, we conjecture that MTP is NP-complete. The existing literature does not contain any work on MTP. The research contributions of this thesis are as follows: We develop new theoretical properties for the solution of STP and devised a new solution approach for it. This approach is based on a novel branch-and-bound (BB) algorithm devised over a reduced solution space. Branching is done using a clustering scheme. Our computational results show that in many cases our approach significantly outperforms the existing Plateau Vertex Traversal and brute force algorithms, especially for problems with many requests appearing in clusters over a large region. We perform a theoretical study of MTP for the first time and prove several theoretical properties for its solution. We have introduced a reduced solution space using these properties. We present the first exact algorithm to solve MTP. This algorithm has a branch-and-bound framework. The reduced solution space calls for a novel branching strategy for MTP. The algorithm has a main branch-and-bound tree with a special structure along with two trees (one for each axis) to store the information required for branching in the main tree in an efficient format. Branching is done using a clustering scheme. We perform computational experiments to evaluate the performance of our algorithm. Our algorithm solves relatively large instances of MTP in a short time.