Convex Optimization Techniques for Geometric Covering Problems

The present thesis is a commencement of a generalization of covering results in specific settings such as the Euclidean space or the sphere to arbitrary compact metric spaces. In particular we consider coverings of compact metric spaces $(X d)$ by balls of radius $r$. We are interested in the minimum number of such balls needed to cover $X$ denoted by $Ncal(X r)$. For finite $X$ this problem coincides with an instance of the combinatorial extsc{set cover} problem which is $mathrm{NP}$-complete. We illustrate approximation techniques based on the moment method of Lasserre for finite graphs and generalize these techniques to compact metric spaces $X$ to obtain upper and lower bounds for $Ncal(X r)$. \ The upper bounds in this thesis follow from the application of a greedy algorithm on the space $X$. Its approximation quality is obtained by a generalization of the analysis of Chvatal's algorithm for the weighted case of extsc{set cover}. We apply this greedy algorithm to the spherical case $X=S^n$ and retrieve the best non-asymptotic bound of Boroczky and Wintsche. Additionally the algorithm can be used to determine coverings of Euclidean space with arbitrary measurable objects having non-empty interior. The quality of these coverings slightly improves a bound of Naszodi. \ For the lower bounds we develop a sequence of bounds $Ncal^t(X r)$ that converge after finitely (say $alphainN$) many steps: $$Ncal^1(X r)leq ldots leq Ncal^alpha(X r)=Ncal(X r).$$ The drawback of this sequence is that the bounds $Ncal^t(X r)$ are increasingly difficult to compute since they are the objective values of infinite-dimensional conic programs whose number of constraints and dimension of underlying cones grow accordingly to $t$. We show that these programs satisfy strong duality and derive a finite dimensional semidefinite program to approximate $Ncal^2(S^2 r)$ to arbitrary precision. Our results rely in part on the moment methods developed by de Laat a