The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

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