In this thesis, we study two problems in combinatorial optimization, the dominating set problem and the robustness problem. In the first half of the thesis, we focus on the dominating set problem in grid graphs and present a distributed algorithm for finding near optimal dominating sets on grids. The dominating set problem is a well-studied mathematical problem in which the goal is to find a minimum size subset of vertices of a graph such that all vertices that are not in that set have a neighbor inside that set. We first provide a simpler proof for an existing centralized algorithm that constructs dominating sets on grids so that the size of the provided dominating set is upper-bounded by the ceiling of (m+2)(n+2)/5 for m by n grids and its difference from the optimal domination number of the grid is upper-bounded by five. We then design a distributed grid domination algorithm to locate mobile agents on a grid such that they constitute a dominating set for it. The basis for this algorithm is the centralized grid domination algorithm. We also generalize the centralized and distributed algorithms for the k-distance dominating set problem, where all grid vertices are within distance k of the vertices in the dominating set. In the second half of the thesis, we study the computational complexity of checking a graph property known as robustness. This property plays a key role in diffusion of information in networks. A graph G=(V,E) is r-robust if for all pairs of nonempty and disjoint subsets of its vertices A,B, at least one of the subsets has a vertex that has at least r neighbors outside its containing set. In the robustness problem, the goal is to find the largest value of r such that a graph G is r-robust. We show that this problem is coNP-complete. En route to showing this, we define some new problems, including the decision version of the robustness problem and its relaxed version in which B=V \ A. We show these two problems are coNP-hard by showing that their complement problems are NP-hard.

Solving NP-hard facility location problems in wireless network planning is a common scenario. In our research, we study the Covering problem, a well known facility location problem with applications in wireless network deployment. We focus on networks with a sparse structure. First, we analyzed two heuristics of building Tree Decomposition based on vertex separator and perfect elimination order. We extended the vertex separator heuristic to improve its time performance. Second, we propose a dynamic programming algorithm based on the Tree Decomposition to solve the Covering problem optimally on the network. We developed several heuristic techniques to speed up the algorithm. Experiment results show that one variant of the dynamic programming algorithm surpasses the performance of the state of the art mathematical optimization commercial software on several occasions. / ix, 89 leaves : ill. ; 29 cm

Recently, interest in the Graphics Processing Unit (GPU) for general purpose parallel applications development and research has grown. Much of the current research on the GPU focuses on the acceleration of regular problems, as irregular problems typically do not provide the same level of performance on the hardware. We explore the potential of the GPU by investigating four problems on the GPU with regular and/or irregular properties: lookback option pricing (regular), single-source shortest path (irregular), maximum flow (irregular), and the task matching problem using multi-swarm particle swarm optimization (regular with elements of irregularity). We investigate the design, implementation, optimization, and performance of these algorithms on the GPU, and compare the results. Our results show that the regular problem achieves greater performance and requires less development effort than the irregular problems. However, we find the GPU to still be capable of providing high levels of acceleration for irregular problems.

No description available.

The traveling salesperson or salesman problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. In addition to vehicle routing, many other applications, e.g., computer wiring, cutting wallpaper, job sequencing or several data visualization techniques, require the solution of a TSP. In this paper we introduce the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem. The package features S3 classes for specifying a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. In addition, it provides an interface to Concorde, one of the best exact TSP solvers currently available. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

In this dissertation we examine several discrete optimization problems through the perspectives of modeling, complexity and algorithms. We first provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the probability that a split cut is better than a type 1 triangle cut is higher than the probability that a type 1 triangle cut is better than a split cut. The analysis also suggests some guidelines on when type 1 triangle cuts are likely to be more effective than split cuts and vice versa. We next study a minimum concave cost network flow problem over a grid network. We give a polytime algorithm to solve this problem when the number of echelons is fixed. We show that the problem is NP-hard when the number of echelons is an input parameter. We also extend our result to grid networks with backward and upward arcs. Our result unifies the complexity results for several models in production planning and green recycling including the lot-sizing model, and gives the first polytime algorithm for some problems whose complexities were not known before. Finally, we examine how much complexity randomness will bring to a simple combinatorial optimization problem. We study a problem called the sell or hold problem (SHP). SHP is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. Although the deterministic version of SHP is trivial to solve, we show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.

Recently, interest in the Graphics Processing Unit (GPU) for general purpose parallel applications development and research has grown. Much of the current research on the GPU focuses on the acceleration of regular problems, as irregular problems typically do not provide the same level of performance on the hardware. We explore the potential of the GPU by investigating four problems on the GPU with regular and/or irregular properties: lookback option pricing (regular), single-source shortest path (irregular), maximum flow (irregular), and the task matching problem using multi-swarm particle swarm optimization (regular with elements of irregularity). We investigate the design, implementation, optimization, and performance of these algorithms on the GPU, and compare the results. Our results show that the regular problem achieves greater performance and requires less development effort than the irregular problems. However, we find the GPU to still be capable of providing high levels of acceleration for irregular problems.

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

For well over 200 years, scientists and doctors have been poking and prodding brains in every which way in an effort to understand how they work. The earliest pokes were quite crude, often involving permanent forms of brain damage. Though neural injury continues to be an active area of research within neuroscience, technology has given neuroscientists a number of tools for stimulating and observing the brain in very subtle ways. Nonetheless, the basic experimental paradigm remains the same; poke the brain and see what happens. For example, neuroscientists studying the visual or auditory system can easily generate any image or sound they can imagine to see how an organism or neuron will respond. Since neuroscientists can now easily design more pokes then they could every deliver, a fundamental question is ``What pokes should they actually use?' The complexity of the brain means that only a small number of the pokes scientists can deliver will produce any information about the brain. One of the fundamental challenges of experimental neuroscience is finding the right stimulus parameters to produce an informative response in the system being studied. This thesis addresses this problem by developing algorithms to sequentially optimize neurophysiology experiments. Every experiment we conduct contains information about how the brain works. Before conducting the next experiment we should use what we have already learned to decide which experiment we should perform next. In particular, we should design an experiment which will reveal the most information about the brain. At a high level, neuroscientists already perform this type of sequential, optimal experimental design; for example crude experiments which knockout entire regions of the brain have given rise to modern experimental techniques which probe the responses of individual neurons using finely tuned stimuli. The goal of this thesis is to develop automated and rigorous methods for optimizing neurophysiology experiments efficiently and at a much finer time scale. In particular, we present methods for near instantaneous optimization of the stimulus being used to drive a neuron.

In this thesis we prove intractability results for well studied problems in computational learning and approximation. Let ε , mu > 0 be arbitrarily small constants and t be an arbitrary constant positive integer. We show an almost optimal hardness factor of d[superscript{1-ε}] for computing an equivalent DNF expression with minimum terms for a boolean function on d variables, given its truth table. In the study of weak learnability, we prove an optimal 1/2 + ε inapproximability for the accuracy of learning an intersection of two halfspaces with an intersection of t halfspaces. Further, we study the learnability of small DNF formulas, and prove optimal 1/2 + ε inapproximability for the accuracy of learning (i) a two term DNF by a t term DNF, and (ii) an AND under adversarial mu-noise by a t-CNF. In addition, we show a 1 - 2[superscript{-d}] + ε inapproximability for accurately learning parities (over GF(2)), under adversarial mu-noise, by degree d polynomials, where d is a constant positive integer. We also provide negative answers to the possibility of stronger semi-definite programming (SDP) relaxations yielding much better approximations for graph partitioning problems such as Maximum Cut and Sparsest Cut by constructing integrality gap examples for them. For Maximum Cut and Sparsest Cut we construct examples -- with gaps alpha[superscript{-1}] - ε (alpha is the Goemans-Williamson constant) and Omega((logloglog n)[superscript{1/13}]) respectively -- for the standard SDP relaxations augmented with O((logloglog n)[superscript{1/6}]) rounds of Sherali-Adams constraints. The construction for Sparsest Cut also implies that an n-point negative type metric may incur a distortion of Omega((logloglog n)[superscript{1/ 13}]) to embed into ell_1 even if the induced submetric on every subset of O((logloglog n)[superscript{1/6}]) points is isometric to ell_1. We also construct an integrality gap of Omega(loglog n) for the SDP relaxation for Uniform Sparsest Cut problem augmented with triangle inequalities, disproving a well known conjecture of Arora, Rao and Vazirani.