Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

2004 - 200922010 - 20111

Settings

Subject: search.filters.subject.Combinatorics

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Combinatorial Methods in Coding Theory
    (2011) Mazumdar, Arya; Barg, Alexander; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This thesis is devoted to a range of questions in applied mathematics and signal processing motivated by applications in error correction, compressed sensing, and writing on non-volatile memories. The underlying thread of our results is the use of diverse combinatorial methods originating in coding theory and computer science. The thesis addresses three groups of problems. The first of them is aimed at the construction and analysis of codes for error correction. Here we examine properties of codes that are constructed using random and structured graphs and hypergraphs, with the main purpose of devising new decoding algorithms as well as estimating the distribution of Hamming weights in the resulting codes. Some of the results obtained give the best known estimates of the number of correctable errors for codes whose decoding relies on local operations on the graph. In the second part we address the question of constructing sampling operators for the compressed sensing problem. This topic has been the subject of a large body of works in the literature. We propose general constructions of sampling matrices based on ideas from coding theory that act as near-isometric maps on almost all sparse signal. This matrices can be used for dimensionality reduction and compressed sensing. In the third part we study the problem of reliable storage of information in non-volatile memories such as flash drives. This problem gives rise to a writing scheme that relies on relative magnitudes of neighboring cells, known as rank modulation. We establish the exact asymptotic behavior of the size of codes for rank modulation and suggest a number of new general constructions of such codes based on properties of finite fields as well as combinatorial considerations.
  • Thumbnail Image
    Item
    Weight Annealing Heuristics for Solving Bin Packing and other Combinatorial Optimization Problems: Concepts, Algorithms and Computational Results
    (2006-10-23) Loh, Kok-Hua; Golden, Bruce L.; Decision and Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The application of weight annealing to combinatorial optimization problems is relatively new, compared to applications of well-known optimization techniques such as simulated annealing and tabu search. The weight annealing approach seeks to expand a neighborhood search by creating distortions in different parts of the search space. Distortion is controlled through weight assignment based on insights gained from one iteration of the search procedure to the next with a view towards focusing computational efforts on the poorly solved regions of the search space. The search for the global optimum should be accelerated and the solution quality should be improved with weight annealing. In this dissertation, we present key ideas behind weight annealing and develop algorithms that solve combinatorial optimization problems. Our weight annealing-based heuristics solve the one-dimensional bin packing problem and the two-dimensional bin packing problem with and without guillotine cutting and item orientation constraints. We also solve the maximum cardinality bin packing problem and the multidimensional multiple knapsack problem with our heuristics.
  • Thumbnail Image
    Item
    On the Generalized Tower of Hanoi Problem I: An Introduction to Cluster Spaces
    (2004-05-04) Rukhin, Andrey; Gasarch, William; Applied Mathematics and Scientific Computation
    In this thesis, we examine the Tower of Hanoi puzzle with p posts (p >= 3) and n disks (n in N). We examine the puzzle in the context of a cluster space: a hierarchical partitioning of the space of all possible disk configurations. This thesis includes two theorems that address the topic of minimal paths connecting disk configurations.