Thesis (M.S.) in Spatial Information Science and Engineering--University of Maine, 2009. / Includes vita. Includes bibliographical references (leaves 94-96).

Thesis (Ph. D.)--University of Washington, 2002. / Vita. Includes bibliographical references (p. 127-134).

Thesis (M.S.)--Kent State University, 2009. / Title from PDF t.p. (viewed Jan. 25, 2010). Advisor: Feodor Dragan. Keywords: greedy routing. Includes bibliographical references (p. 76-77).

This dissertation uses theoretical and empirical tools to answer applied questions of design with an emphasis on issues relating to safety and crime. The first essay incorporates safety in implementation theory and studies when and how safe mechanisms can be designed to obtain socially desirable outcomes. I provide general conditions under which a social choice rule can be implemented using safe mechanisms. The second essay is an empirical study of how criminals respond to changing profitability of crime, a question that informs the policy debate on the most effective crime fighting methods. I find that the price elasticity of theft is about 1 in the short term and increases to about 1.2 over a seven-month horizon, suggesting that policies that directly affect crime profitability, such as policies that shut down black markets or those that reduce demand for illegal goods, can be relatively effective. The third essay shows that any standard implementation problem can be formulated as a question about the existence of a graph that solves a graph coloring problem, establishing a connection between implementation theory and graph theory. More generally, an implementation problem can be viewed as a constraint satisfaction problem, and I propose an algorithm to design simple mechanisms to solve arbitrary implementation problems. / text

Data dissemination among wireless devices is an essential application in wireless networks. In contrast to its wired counterparts which have more stable network settings, wireless networks are subject to network dynamics, such as variable network topology, channel availability and capacity, which are due to user mobility, signal collision, random channel fading and scattering, etc. Network dynamics complicate the protocol design for optimal data disseminations. Although the topic has been intensively discussed for many years, existing solutions are still not completely satisfactory, especially for stochastic or arbitrary networks. In this thesis, we address optimal data dissemination in both stochastic and arbitrary wireless networks, using techniques of Lyapunov optimization, graph theory, network coding, multi-resolution coding and successive interference cancellation. We first discuss the maximization of time-averaged throughput utility over a long run for unicast and multirate multicast, respectively, in stochastic wireless networks without probing into the future. For multi-session unicast communications, a utility-maximizing cross-layer design, composed of joint end-to-end rate control, routing, and channel allocation, is proposed for cognitive radio networks with stochastic primary user occupations. Then, we study optimal multirate multicast to receivers with non-uniform receiving rates, also making dynamic cross-layer decisions, in a general wireless network with both a timevarying topology and random channel capacities, by utilizing random linear network coding and multi-resolution coding. In both solutions, we assume users are selfish and prefer only to relay data for others with strong social ties. Such social selfishness of users is a new constraint in network protocol design. Its impact on efficient data dissemination in wireless networks is largely unstudied, especially under stochastic settings. Lyapunov optimization is applied in our protocol design achieving close-to-optimal utilities. Next, we turn to latency-minimizing data aggregation in wireless sensor networks having arbitrary network topologies under the physical interference model. Different from our effort for stochastic networks where we target at time-averaged optimality over a long run, the objective here is to minimize the time-span to accomplish one round of aggregation scheduling for all sensors in an arbitrary topology. This problem is NP-hard, involving both aggregation tree construction and collision-free link scheduling. The current literature mostly considers the protocol interference model, which has been shown to be less practical than the physical interference model in characterizing the interference relations in the real world. A distributed solution under the physical interference model is challenging since cumulative interferences from all concurrently transmitting devices need to be well measured. In this thesis, we present a distributed aggregation protocol with an improved approximation ratio as compared with previous work. We then discuss the tradeoff between aggregation latency and energy consumption for arbitrary topologies when the successive interference cancellation technique is in force. Another distributed algorithm is introduced with asymptotic optimality in both aggregation latency and latency-energy tradeoff. Through theoretical analysis and empirical study, we rigorously examine the optimality of our protocols comparing with both the theoretical optima and existing solutions. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Given an undirected graph G(V,E) and a vertex subset U\subseteq V the U-space is the vector space over GF(2) spanned by the paths with end-points in U and the cycles in G(V,E). We extend Vismara's algorithm to the computation of the union of all minimum length bases of the U-space. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c^k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n^k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.

The massive growth and proliferation of media, content, and services on the Internet are driving the need for more network capacity as well as larger networks. With increasing bandwidth and transmission speeds, even small disruptions in service can result in a significant loss of data. Thus, it is becoming increasingly important to monitor networks for their performance and to be able to handle failures effectively. Doing so is beneficial from a network design perspective as well as in being able to provide a richer experience to the users of such networks. Network tomography refers to inference problems in large-scale networks wherein it is of interest to infer individual characteristics, such as link delays, through aggregate measurements, such as end-to-end path delays. In this dissertation, we establish a fundamental theory for a class of network tomography problems in which the link metrics of a network are modeled to be additive. We establish the necessary and sufficient conditions on the network topology, provide polynomial time graph algorithms that quantify the extent of identifiability, and algorithms to identify the unknown link metrics. We develop algorithms for all graph topologies classified on the basis of their connectivity. The solutions developed in this dissertation extend beyond networking and are applicable in areas such as nano-electronics and power systems. We then develop graph algorithms to handle link failures effectively and to provide multipath routing capabilities in IP as well as Ethernet based networks. Our schemes guarantee recovery and are designed to pre-compute alternate next hops that can be taken upon link failures. This allows for fast re-routing as we avoid the need to wait for (control plane) re-computations.

No description available.

La capture du mouvement est un défi majeur dans le cadre de la modélisation d'objets articulés. Ce problème implique la recherche de correspondances entre objets vus dans des images différentes. On propose trois approches pour résoudre ce problème basé sur des techniques de vision par ordinateur et la théorie spectrale des graphes. La première consiste à modéliser une scène 3D à l'aide d'une collection de points. On propose deux extensions de l'algorithme de Lucas-Kanade pour tracker des caractéristiques de manière efficace et pour estimer le "scene-flow". La deuxième approche basée sur la théorie spectrale des graphes cherche à établir des correspondances entre des objets représentés par des graphes. Finalement on s'intéresse au problème de segmentation qui soit cohérente dans le temps et notre approche est basée sur une méthode de clustering spectral appliquée à une séquence temporelle.