Convex Optimization Techniques for Geometric Covering Problems, ISBN: 9783754346754
Convex Optimization Techniques for Geometric Covering Problems
  • By (author) Rolfes Jan Hendrik

Available for Order

HKD $140.00

within 14 to 24 business days
Brief Description

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 \textsc{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 Chv\'atal's algorithm for the weighted case of \textsc{set cover}. We apply this greedy algorithm to the spherical case $X=S^n$ 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 $\Ncal^t(X, r)$ that converge after finitely (say $\alpha\in\N$) 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


Book Details
Publisher:
Books On Demand
Binding:
Paperback
Date of Pub.:
Sep 15, 2021
Edition:
edition
Language:
-
ISBN:
9783754346754
Dimensions:
-
Weights:
240.40g
Contact Us
Contact Person
Ms. Annie Chau
Email Address
annie.chau@apbookshop.com
Fax No.
+852 2391-7430
Office Hours
Mon to Fri: 9am to 6pm
Sat, Sun and Public Holidays: Closed
General Enquiry
This site use cookies. By continuing to browse this site you are agreeing to our use of cookies.