Convex Optimization Techniques for Geometric Covering Problems - Jan Hendrik Rolfes

. .

Résumé :
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 dollars(X,d) dollars by balls of radius dollarsr dollars. We are interested in the minimum number of such balls needed to cover dollarsX dollars, denoted by dollars\Ncal(X,r) dollars. For finite dollarsX dollars this problem coincides with an instance of the combinatorial \textsc{set cover} problem, which is dollars\mathrm{NP} dollars-complete. We illustrate approximation techniques based on the moment method of Lasserre for finite graphs and generalize these techniques to compact metric spaces dollarsX dollars to obtain upper and lower bounds for dollars\Ncal(X,r) dollars. \\ The upper bounds in this thesis follow from the application of a greedy algorithm on the space dollarsX dollars. Its approximation quality is obtained by a generalization of the analysis of Chv\'atal's algorithm for the weighted case of \textsc{set cover}. We apply this greedy algorithm to the spherical case dollarsX=S^n dollars and retrieve the best non-asymptotic bound of B\or\oczky 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 Nasz\'odi. \\ For the lower bounds we develop a sequence of bounds dollars\Ncal^t(X,r) dollars that converge after finitely (say dollars\alpha\in\N dollars) many steps: dollars dollars\Ncal^1(X,r)\leq \ldots \leq \Ncal^\alpha(X,r)=\Ncal(X,r). dollars dollars The drawback of this sequence is that the bounds dollars\Ncal^t(X,r) dollars 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 dollarst dollars. We show that these programs satisfy strong duality and derive a finite dimensional semidefinite program to approximate dollars\Ncal^2(S^2,r) dollars to arbitrary precision. Our results rely in part on the moment methods developed by de Laat and Vallentin for the packing problem on topological packing graphs. However, in the covering problem we have to deal with two types of constraints instead of one type as in packing problems and consequently additional work is required.