No description available.

Graph-partitioning problems are a central topic of research in the study of algorithms and complexity theory. They are of interest to theoreticians with connections to error correcting codes, sampling algorithms, metric embeddings, among others, and to practitioners, as algorithms for graph partitioning can be used as fundamental building blocks in many applications. One of the central problems studied in this field is the sparsest cut problem, where we want to compute the cut which has the least ratio of number of edges cut to size of smaller side of the cut. This ratio is known as the expansion of the cut. In spite of over 3 decades of intensive research, the approximability of this parameter remains an open question. The study of this optimization problem has lead to powerful techniques for both upper bounds and lower bounds for various other problems, and interesting conjectures such as the SSE conjecture. Cheeger's Inequality, a central inequality in Spectral Graph Theory, establishes a bound on expansion via the spectrum of the graph. This inequality and its many (minor) variants have played a major role in the design of algorithms as well as in understanding the limits of computation. In this thesis we study three notions of expansion, namely edge expansion in graphs, vertex expansion in graphs and hypergraph expansion. We define suitable notions of spectra w.r.t. these notions of expansion. We show how the notion Cheeger's Inequality goes across these three problems. We study higher order variants of these notions of expansion (i.e. notions of expansion corresponding to partitioning the graph/hypergraph into more than two pieces, etc.) and relate them to higher eigenvalues of graphs/hypergraphs. We also study approximation algorithms for these problems. Unlike the case of graph eigenvalues, the eigenvalues corresponding to vertex expansion and hypergraph expansion are intractable. We give optimal approximation algorithms and computational lower bounds for computing them.

Controlling a system with control and state constraints is one of the most important problems in control theory, but also one of the most challenging. Another important but just as demanding topic is robustness against uncertainties in a controlled system. One of the most successful approaches, both in theory and practice, to control constrained systems is model predictive control (MPC). The basic idea in MPC is to repeatedly solve optimization problems on-line to find an optimal input to the controlled system. In recent years, much effort has been spent to incorporate the robustness problem into this framework. The main part of the thesis revolves around minimax formulations of MPC for uncertain constrained linear discrete-time systems. A minimax strategy in MPC means that worst-case performance with respect to uncertainties is optimized. Unfortunately, many minimax MPC formulations yield intractable optimization problems with exponential complexity. Minimax algorithms for a number of uncertainty models are derived in the thesis. These include systems with bounded external additive disturbances, systems with uncertain gain, and systems described with linear fractional transformations. The central theme in the different algorithms is semidefinite relaxations. This means that the minimax problems are written as uncertain semidefinite programs, and then conservatively approximated using robust optimization theory. The result is an optimization problem with polynomial complexity. The use of semidefinite relaxations enables a framework that allows extensions of the basic algorithms, such as joint minimax control and estimation, and approx- imation of closed-loop minimax MPC using a convex programming framework. Additional topics include development of an efficient optimization algorithm to solve the resulting semidefinite programs and connections between deterministic minimax MPC and stochastic risk-sensitive control. The remaining part of the thesis is devoted to stability issues in MPC for continuous-time nonlinear unconstrained systems. While stability of MPC for un-constrained linear systems essentially is solved with the linear quadratic controller, no such simple solution exists in the nonlinear case. It is shown how tools from modern nonlinear control theory can be used to synthesize finite horizon MPC controllers with guaranteed stability, and more importantly, how some of the tech- nical assumptions in the literature can be dispensed with by using a slightly more complex controller.

In order to predict and analyze the performance of both floating point and integer line drawing algorithms the performance of individual instructions is examined. A select group of line drawing algorithms are implemented and timed in performance tests. An algorithms accuracy is observed along with its performance in three tests. These tests are performed on five computers for comparison. The effects of utilizing the standard code optimizer is included as an integral part of the research. / Department of Computer Science

In today's high-tech industrialized world, we are always looking for faster, and more reliable ways to produce goods. Robotics offers us a possible replacement for the human worker, but can a robot reliably perform the same tasks as a human arm, for example?The complex problem of teaching a robot to move it's hand in some well defined path can be broken down into a variety of algorithms. These path control algorithms generally compute some path description equation, which is used to generate path points either in terms of the Cartesian coordinates of the robot's work cell or the robot's joint variables. Common functions used in the path generation process include cubic spline functions and linear functions.This research project tests a variety of algorithms on a relatively simple robot in order to perform the task of drawing shapes (lines, squares, circles) on planes (horizontal and vertical) in the workcell. By studying the paths drawn we can determine the effect of each algorithm on the path control process, as well as the effect of plane positioning, robot structure, and the robot's controller. / Department of Computer Science

The study of graph theory and its applications have increased substantially in the past 40 years. This is especially the case in the applications to the fields of computer science, electrical, and industrial engineering. Applications vary from designing computer software and hardware to telephone networks to airline network.In the thesis, properties are studied in detail to include definitions, theorems, examples and implementations of four graph algorithms in two important topics, namely connectivity and shortest paths. In the implementation part, algorithms will be available to solve problems on selected graphs. A graphic representation is also included to have a better picture of a problem and its solution. / Department of Computer Science

We study group-summarization of probabilistic graphs that naturally arise in social networks, semistructured data, and other applications. Our proposed framework groups the nodes and edges of the graph based on a user selected set of node attributes. We present methods to compute useful graph aggregates without the need to create all of the possible graph-instances of the original probabilistic graph. Also, we present an algorithm for graph summarization based on pure relational (SQL) technology. We analyze our algorithm and practically evaluate its efficiency using an extended Epinions dataset as well as synthetic datasets. The experimental results show the scalability of our algorithm and its efficiency in producing highly compressed summary graphs in reasonable time. / Graduate

In this work, we classify the shortest path problems, review all source algorithms and analyse the different implementations of single source algorithms using various list structures and labelling techniques. Furthermore, we study the Sensitivity Analysis of one-to-all problems and present an algorithm, Senet, for their Post Optimality Analysis. Senet determines all the critical values for the weight of an arc (which could be optimal, non-optimal or non-existant) at which the optimal solution changes. Senet also provides the updated optimal solution for every range formed by two successive critical values.

No description available.

No description available.