In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within $2^{\log^{1-1/{(\log\log m)^c}}m}$ in polynomial time for any constant $c < 1/2$, unless $P=NP$, when the given objects are $m$ triangles or convex objects. This shows that Red-Blue Geometric Set Cover is a harder problem than Geometric Set Cover for some class of objects. \item Boxes Class Cover is APX-hard. \end{itemize} We also define MaxRM-3SAT, a restricted version of Max3SAT, and we prove that this problem is APX-hard. This problem might be interesting in its own right.\\ In the distributed setting, we define a new model, the fixed-link model, where each processor has a position on the plane and processors can communicate to each other if and only if there is an edge between them. We motivate the model and study a number of geometric problems in this model. We prove lower bounds on the communication complexity of the problems in the fixed-link model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm in the fixed-link model with $n$ nodes to solve the following problems, when the communication is in the asynchronous KT1 model: \begin{itemize} \item $\Omega(n^2/\log n)$ expected bits of communication are required for solving Diameter, Convex Hull, or Closest Pair, even if the graph has only a linear number of edges. \item $\Omega( min\{n^2,1/\epsilon\})$ expected bits of communications are required for approximating Diameter within a $1-\epsilon$ factor of optimal, even if the graph is planar. \item $\Omega(n^2)$ bits of communications is required for approximating Closest Pair in a graph on an $[n^c] \times [n^c]$ grid, for any constant $c>1+1/(2\lg n)$, within $\frac{n^{c-1/2}}{4}-\epsilon$ factor of optimal, even if the graph is planar. \end{itemize} We also present approximation algorithms in geometric communication networks with $n$ nodes, when the communication is in the asynchronous CONGEST KT1 model: \begin{itemize} \item An $\epsilon$-kernel, and consequently $(1-\epsilon)$-\diamapprox~ and \ep -Approximate Hull with $O(\frac{n}{\sqrt{\epsilon}})$ messages plus the costs of constructing a spanning tree. \item An $\frac{n^c}{\sqrt{\frac{k}{2}}}$-Approximate Closest Pair on an $[n^c] \times [n^c]$ grid , for a constant $c>1/2$, plus the cost of computing a spanning tree, for any $k\leq {n-1}$. \end{itemize} We also define a new version of the two-party communication problem, Path Computation, where two parties communicate through a path. We prove a lower bound on the communication complexity of this problem. / Graduate

No description available.

Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique. / Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs.

Durant les dernières années, la taille des systèmes ainsi que leur complexité ont pas mal évolué, entrainant le besoin d'approches distribuées pour la commande et l'aide à la décision. Cette thèse porte sur la résolution d'un problème incluant une commande distribuée et une aide à la décision, l'allocation dynamique de ressource dans un réseau.Pour résoudre ce problème, nous avons étudié un algorithme basé sur un consensus qui ne nécessite pas de calcul centralisé, et qui soit capable de traiter des applications modélisées par des systèmes dynamiques ou par des fonctions sans mémoires. La principale contribution de ce travail de thèse est d'avoir prouvé, en utilisant des outils issus de la théorie des graphes etl'analyse de la passivité, que le contrôleur atteint la solution optimale de façon asymptotique, sans obligation d'avoir une information complète.Afin d'illustrer la pertinence de notre résultat principal, plusieurs applications en ingénierie ont été étudiées, incluant la commande distribuée pour l'économie d'énergie dans des bâtiments intelligents, la gestion des clients dans un environnement de "smart grids", et le développement d'une méthode exacte d'optimisation distribuée pour un problème d'allocation de ressources soumis à des contraintes sur les bornes inférieures.Enfin, nous étudions les techniques d'allocation de ressources basées sur les modèlesde dynamique de populations. Pour les rendre distribuées, nous introduisons le concept dedynamique de populations "pas bien mélangées". Nous montrons que ces dynamiques peuventêtre utilisées pour des structures d'informations contraintes. Même si les dynamiquesde populations "pas bien mélangées" utilisent des informations partielles, ellesconservent des propriétés similaires aux dynamiques classiques qui utilisent desinformations complètes. Plus spécifiquement, la conservation de masse et la convergencevers l'équilibre de Nash sont prouvées. / Since the complexity and scale of systems have been growing in the last years, distributed approaches for control and decision making are becoming more prevalent. This dissertation focuses on an important problem involving distributed control and decision making, the dynamic resource allocation in a network. To address this problem, we explore a consensus--based algorithm that does not require any centralized computation, and that is capable to deal with applications modeled either by dynamical systems or by memoryless functions. The main contribution of our research is to prove, by means of graph theoretical tools and passivity analysis, that the proposed controller asymptotically reaches an optimal solution without the need of full information. In order to illustrate the relevance of our main result, we address several engineering applications including: distributed control for energy saving in smart buildings, management of the customers of an aggregating entity in a smart grid environment, and development of an exact distributed optimization method that deals with resource allocation problems subject to lower--bound constraints. Finally, we explore resource allocation techniques based on classic population dynamics models. In order to make them distributed, we introduce the concept of non--well--mixed population dynamics. We show that these dynamics are capable to deal with constrained information structures that are characterized by non--complete graphs. Although the proposed non--well--mixed population dynamics use partial information, they preserve similar properties of their classic counterpart, which uses full information. Specifically, we prove mass conservation and convergence to Nash equilibrium. / Dado que la complejidad y la escala de los sistemas sehan ido incrementando en los últimos años, las técnicas centralizadas de control y toma de decisiones están siendo reemplazadas por métodos distribuidos. Esta tesis se centra en un importante problema que involucra control y toma de decisiones distribuidas: la asignación dinámica de recursos en redes. Para abordar este problema, exploramos un algoritmo basado en consenso que no requiere computación centralizada, y que puede ser usado en aplicaciones modeladas ya sea por sistemas dinámicos o funciones sin memoria. La principal contribución de esta tesis es probar, por medio de teoría de grafos y pasividad, que el algoritmo propuesto alcanza asintóticamente una solución óptima sin la necesidad de usar información completa. Para ilustrar la relevancia del resultado principal de esta disertación, abordamos varias aplicaciones en ingeniería,incluyendo: el control distribuido en edificios inteligentes orientado a la eficiencia energética, la gestión de los clientes de un agregador en una red inteligente en la que se aplican estrategias de respuesta de la demanda, y el desarrollo de un método de optimización exacto que permite incluir restricciones de límite inferior. Finalmente, se exploran otras técnicas de asignación derecursos inspiradas en modelos de dinámicas poblacionales. Se introduce el concepto de poblaciones no—bien—mezcladas, y se muestra que las dinámicas asociadas a este tipo de poblaciones cuentan con una estructura de información local, caracterizada por grafos que no son completos. A pesar de que las dinámicas propuestas usan información parcial, ellas preservan características similares a las dinámicas poblacionales clásicas que usan información completa.

<p dir="ltr">Autonomous robots can perform dangerous and tedious tasks, eliminating the need for human involvement. To deploy an autonomous robot in the field, a typical planning and control hierarchy is used, consisting of a high-level planner, a mid-level motion planner, and a low-level tracking controller. In applications such as simultaneous localization and mapping, package delivery, logistics, and surveillance, a group of autonomous robots can be more efficient and resilient than a single robot. However, deploying a multi-robot team by directly aggregating each robot's planning hierarchy into a larger, centralized hierarchy faces challenges related to scalability, resilience, and real-time computation. Distributed algorithms offer a promising solution for introducing effective coordination within a network of robots, addressing these issues. This thesis explores the application of distributed algorithms in multi-robot systems, focusing on several essential components required to enable distributed multi-robot coordination, both in general terms and for specific applications.</p>