Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;??)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

In this work we formalize a new natural objective (or cost) function for bi-clustering - Monochromatic bi-clustering. Our objective function is suitable for detecting meaningful homogenous clusters based on categorical valued input matrices. Such problems have arisen recently in systems biology where researchers have inferred functional classifications of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problems. We show that finding optimal solutions is NP-hard and complement this result by introducing a polynomial time approximation algorithm for this bi-clustering task. This is the first positive approximation guarantee for bi-clustering algorithms. We also show that bi-clustering with our objective function can be viewed as a generalization of correlation clustering.

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;²)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

In this work we formalize a new natural objective (or cost) function for bi-clustering - Monochromatic bi-clustering. Our objective function is suitable for detecting meaningful homogenous clusters based on categorical valued input matrices. Such problems have arisen recently in systems biology where researchers have inferred functional classifications of biological agents based on their pairwise interactions. We analyze the computational complexity of the resulting optimization problems. We show that finding optimal solutions is NP-hard and complement this result by introducing a polynomial time approximation algorithm for this bi-clustering task. This is the first positive approximation guarantee for bi-clustering algorithms. We also show that bi-clustering with our objective function can be viewed as a generalization of correlation clustering.

No description available.

No description available.

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.

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.