Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are covered. Rule (2) is called the propagation rule, and it is applied iteratively. Throughout, we use $n$ to denote the number of nodes in the input graph. We prove that the path-width parameter is a lower bound for the optimal value. We show that the Propagation problem is NP-hard in planar weighted graphs. We prove that it is NP-hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in weighted (general) graphs. The second problem that we study is the Power Dominating Set problem. This problem has two covering rules. The first rule is the same as the domination rule as in the Dominating Set problem, and the second rule is the same propagation rule as in the Propagation problem. We show that it is hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in general graphs. We design and analyze an approximation algorithm with a performance guarantee of $O(\sqrt{n})$ on planar graphs. We formulate a common generalization of the above two problems called the General Propagation problem. We reformulate this general problem as an orientation problem, and based on this reformulation we design a dynamic programming algorithm. The algorithm runs in linear time when the graph has tree-width $O(1)$. Motivated by applications, we introduce a restricted version of the problem that we call the $\ell$-round General Propagation problem. We give a PTAS for the $\ell$-round General Propagation problem on planar graphs, for small values of $\ell$. Our dynamic programming algorithms and the PTAS can be extended to other problems in networks with similar propagation rules. As an example we discuss the extension of our results to the Target Set Selection problem in the threshold model of the diffusion processes. In the second part of the thesis, we focus on the Steiner Tree Packing problem. In this problem, we are given a graph $G$ and a subset of terminal nodes $R\subseteq V(G)$. The goal in this problem is to find a maximum cardinality set of disjoint trees that each spans $R$, that is, each of the trees should contain all terminal nodes. In the edge-disjoint version of this problem, the trees have to be edge disjoint. In the element-disjoint version, the trees have to be node disjoint on non-terminal nodes and edge-disjoint on edges adjacent to terminals. We show that both problems are NP-hard when there are only $3$ terminals. Our main focus is on planar instances of these problems. We show that the edge-disjoint version of the problem is NP-hard even in planar graphs with $3$ terminals on the same face of the embedding. Next, we design an algorithm that achieves an approximation guarantee of $\frac{1}{2}-\frac{1}{k}$, given a planar graph that is $k$ element-connected on the terminals; in fact, given such a graph the algorithm returns $k/2-1$ element-disjoint Steiner trees. Using this algorithm we get an approximation algorithm with guarantee of (almost) $4$ for the edge-disjoint version of the problem in planar graphs. We also show that the natural LP relaxation of the edge-disjoint Steiner Tree Packing problem has an integrality ratio of $2-\epsilon$ in planar graphs.

This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph $G$ and the goal is to find a minimum-sized set of nodes $S$ that covers all of the nodes, where a node $v$ is covered if (1) $v$ is in $S$, or (2) $v$ has a neighbor $u$ such that $u$ and all of its neighbors except $v$ are covered. Rule (2) is called the propagation rule, and it is applied iteratively. Throughout, we use $n$ to denote the number of nodes in the input graph. We prove that the path-width parameter is a lower bound for the optimal value. We show that the Propagation problem is NP-hard in planar weighted graphs. We prove that it is NP-hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in weighted (general) graphs. The second problem that we study is the Power Dominating Set problem. This problem has two covering rules. The first rule is the same as the domination rule as in the Dominating Set problem, and the second rule is the same propagation rule as in the Propagation problem. We show that it is hard to approximate the optimal value to within a factor of $2^{\log^{1-\epsilon}{n}}$ in general graphs. We design and analyze an approximation algorithm with a performance guarantee of $O(\sqrt{n})$ on planar graphs. We formulate a common generalization of the above two problems called the General Propagation problem. We reformulate this general problem as an orientation problem, and based on this reformulation we design a dynamic programming algorithm. The algorithm runs in linear time when the graph has tree-width $O(1)$. Motivated by applications, we introduce a restricted version of the problem that we call the $\ell$-round General Propagation problem. We give a PTAS for the $\ell$-round General Propagation problem on planar graphs, for small values of $\ell$. Our dynamic programming algorithms and the PTAS can be extended to other problems in networks with similar propagation rules. As an example we discuss the extension of our results to the Target Set Selection problem in the threshold model of the diffusion processes. In the second part of the thesis, we focus on the Steiner Tree Packing problem. In this problem, we are given a graph $G$ and a subset of terminal nodes $R\subseteq V(G)$. The goal in this problem is to find a maximum cardinality set of disjoint trees that each spans $R$, that is, each of the trees should contain all terminal nodes. In the edge-disjoint version of this problem, the trees have to be edge disjoint. In the element-disjoint version, the trees have to be node disjoint on non-terminal nodes and edge-disjoint on edges adjacent to terminals. We show that both problems are NP-hard when there are only $3$ terminals. Our main focus is on planar instances of these problems. We show that the edge-disjoint version of the problem is NP-hard even in planar graphs with $3$ terminals on the same face of the embedding. Next, we design an algorithm that achieves an approximation guarantee of $\frac{1}{2}-\frac{1}{k}$, given a planar graph that is $k$ element-connected on the terminals; in fact, given such a graph the algorithm returns $k/2-1$ element-disjoint Steiner trees. Using this algorithm we get an approximation algorithm with guarantee of (almost) $4$ for the edge-disjoint version of the problem in planar graphs. We also show that the natural LP relaxation of the edge-disjoint Steiner Tree Packing problem has an integrality ratio of $2-\epsilon$ in planar graphs.

Given a finite set K of terminals in the plane. A rectilinear Steiner minimum tree for K (RST) is a tree which interconnects among these terminals using only horizontal and vertical lines of shortest possible length containing Steiner point. We show the complexity of RST i.e. belongs to NP-complete. Moreover we present an approximative method of determining the solution of RST problem proposed by Sanjeev Arora in 1996, Arora's Approximation Scheme. This algorithm has time complexity polynomial in the number of terminals for a fixed performance ratio 1 + Epsilon.

This PhD thesis consists of a summary and four papers which deal with stochastic approximation algorithms and first-passage percolation. Paper I deals with the a.s. limiting properties of bounded stochastic approximation algorithms in relation to the equilibrium points of the drift function. Applications are given to some generalized Pólya urn processes. Paper II continues the work of Paper I and investigates under what circumstances one gets asymptotic normality from a properly scaled algorithm. The algorithms are shown to converge in some other circumstances, although the limiting distribution is not identified. Paper III deals with the asymptotic speed of first-passage percolation on a graph called the ladder when the times associated to the edges are independent, exponentially distributed with the same intensity. Paper IV generalizes the work of Paper III in allowing more edges in the graph as well as not having all intensities equal.

Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

abstract: Semiconductor scaling technology has led to a sharp growth in transistor counts. This has resulted in an exponential increase on both power dissipation and heat flux (or power density) in modern microprocessors. These microprocessors are integrated as the major components in many modern embedded devices, which offer richer features and attain higher performance than ever before. Therefore, power and thermal management have become the significant design considerations for modern embedded devices. Dynamic voltage/frequency scaling (DVFS) and dynamic power management (DPM) are two well-known hardware capabilities offered by modern embedded processors. However, the power or thermal aware performance optimization is not fully explored for the mainstream embedded processors with discrete DVFS and DPM capabilities. Many key problems have not been answered yet. What is the maximum performance that an embedded processor can achieve under power or thermal constraint for a periodic application? Does there exist an efficient algorithm for the power or thermal management problems with guaranteed quality bound? These questions are hard to be answered because the discrete settings of DVFS and DPM enhance the complexity of many power and thermal management problems, which are generally NP-hard. The dissertation presents a comprehensive study on these NP-hard power and thermal management problems for embedded processors with discrete DVFS and DPM capabilities. In the domain of power management, the dissertation addresses the power minimization problem for real-time schedules, the energy-constrained make-span minimization problem on homogeneous and heterogeneous chip multiprocessors (CMP) architectures, and the battery aware energy management problem with nonlinear battery discharging model. In the domain of thermal management, the work addresses several thermal-constrained performance maximization problems for periodic embedded applications. All the addressed problems are proved to be NP-hard or strongly NP-hard in the study. Then the work focuses on the design of the off-line optimal or polynomial time approximation algorithms as solutions in the problem design space. Several addressed NP-hard problems are tackled by dynamic programming with optimal solutions and pseudo-polynomial run time complexity. Because the optimal algorithms are not efficient in worst case, the fully polynomial time approximation algorithms are provided as more efficient solutions. Some efficient heuristic algorithms are also presented as solutions to several addressed problems. The comprehensive study answers the key questions in order to fully explore the power and thermal management potentials on embedded processors with discrete DVFS and DPM capabilities. The provided solutions enable the theoretical analysis of the maximum performance for periodic embedded applications under power or thermal constraints. / Dissertation/Thesis / Ph.D. Computer Science 2012

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code (propriété de domination) et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code (propriété de séparation). Dans cette thèse, nous nous intéressons à des aspects combinatoires et algorithmiques relatifs aux codes identifiants.Pour la partie combinatoire, nous étudions tout d'abord des questions extrémales en donnant une caractérisation complète des graphes non-orientés finis ayant comme taille minimum de code identifiant leur ordre moins un. Nous caractérisons également les graphes dirigés finis, les graphes non-orientés infinis et les graphes orientés infinis ayant pour seul code identifiant leur ensemble de sommets. Ces résultats répondent à des questions ouvertes précédemment étudiées dans la littérature.Puis, nous étudions la relation entre la taille minimum d'un code identifiant et le degré maximum d'un graphe, en particulier en donnant divers majorants pour ce paramètre en fonction de l'ordre et du degré maximum. Ces majorants sont obtenus via deux techniques. L'une est basée sur la construction d'ensembles indépendants satisfaisant certaines propriétés, et l'autre utilise la combinaison de deux outils de la méthode probabiliste : le lemme local de Lovasz et une borne de Chernoff. Nous donnons également des constructions de familles de graphes en relation avec ce type de majorants, et nous conjecturons que ces constructions sont optimales à une constante additive près.Nous présentons également de nouveaux minorants et majorants pour la cardinalité minimum d'un code identifiant dans des classes de graphes particulières. Nous étudions les graphes de maille au moins 5 et de degré minimum donné en montrant que la combinaison de ces deux paramètres influe fortement sur la taille minimum d'un code identifiant. Nous appliquons ensuite ces résultats aux graphes réguliers aléatoires. Puis, nous donnons des minorants pour la taille d'un code identifiant des graphes d'intervalles et des graphes d'intervalles unitaires. Enfin, nous donnons divers minorants et majorants pour cette quantité lorsque l'on se restreint aux graphes adjoints. Cette dernière question est abordée via la notion nouvelle de codes arête-identifiants.Pour la partie algorithmique, il est connu que le problème de décision associés à la notion de code identifiant est NP-complet même pour des classes de graphes restreintes. Nous étendons ces résultats à d'autres classes de graphes telles que celles des graphes split, des co-bipartis, des adjoints ou d'intervalles. Pour cela nous proposons des réductions polynomiales depuis divers problèmes algorithmiques classiques. Ces résultats montrent que dans beaucoup de classes de graphes, le problème des codes identifiants est algorithmiquement plus difficile que des problèms liés (tel que le problème des ensembles dominants).Par ailleurs, nous complétons les connaissances relatives à l'approximabilité du problème d'optimisation associé aux codes identifiants. Nous étendons le résultat connu de NP-difficulté pour l'approximation de ce problème avec un facteur sous-logarithmique (en fonction de la taille du graphe instance) aux graphes bipartis, split et co-bipartis, respectivement. Nous étendons également le résultat connu d'APX-complétude pour les graphes de degré maximum donné à une sous-classe des graphes split, aux graphes bipartis de degré maximum 4 et aux graphes adjoints. Enfin, nous montrons l'existence d'un algorithme de type PTAS pour les graphes d'intervalles unitaires. / An identifying code is a set of vertices of a graph such that, on the one hand, each vertex out of the code has a neighbour in the code (domination property), and, on the other hand, all vertices have a distinct neighbourhood within the code (separation property). In this thesis, we investigate combinatorial and algorithmic aspects of identifying codes.For the combinatorial part, we first study extremal questions by giving a complete characterization of all finite undirected graphs having their order minus one as minimum size of an identifying code. We also characterize finite directed graphs, infinite undirected graphs and infinite oriented graphs having their whole vertex set as unique identifying code. These results answer open questions that were previously studied in the literature.We then study the relationship between the minimum size of an identifying code and the maximum degree of a graph. In particular, we give several upper bounds for this parameter as a function of the order and the maximum degree. These bounds are obtained using two techniques. The first one consists in the construction of independent sets satisfying certain properties, and the second one is the combination of two tools from the probabilistic method: the Lovasz local lemma and a Chernoff bound. We also provide constructions of graph families related to this type of upper bounds, and we conjecture that they are optimal up to an additive constant.We also present new lower and upper bounds for the minimum cardinality of an identifying code in specific graph classes. We study graphs of girth at least 5 and of given minimum degree by showing that the combination of these two parameters has a strong influence on the minimum size of an identifying code. We apply these results to random regular graphs. Then, we give lower bounds on the size of a minimum identifying code of interval and unit interval graphs. Finally, we prove several lower and upper bounds for this parameter when considering line graphs. The latter question is tackled using the new notion of an edge-identifying code.For the algorithmic part, it is known that the decision problem associated to the notion of an identifying code is NP-complete, even for restricted graph classes. We extend the known results to other classes such as split graphs, co-bipartite graphs, line graphs or interval graphs. To this end, we propose polynomial-time reductions from several classical hard algorithmic problems. These results show that in many graph classes, the identifying code problem is computationally more difficult than related problems (such as the dominating set problem).Furthermore, we extend the knowledge of the approximability of the optimization problem associated to identifying codes. We extend the known result of NP-hardness of approximating this problem within a sub-logarithmic factor (as a function of the instance graph) to bipartite, split and co-bipartite graphs, respectively. We also extendthe known result of its APX-hardness for graphs of given maximum degree to a subclass of split graphs, bipartite graphs of maximum degree 4 and line graphs. Finally, we show the existence of a PTAS algorithm for unit interval graphs.

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.