Item

Abstract

This thesis deals with a number of geometric optimization problems which are all NP-hard. The first problem we consider is the set cover problem for polytopes in R3. Here, we are given a set of points in R3 and a fixed set of translates of an arbitrary polytope. We would like to select a subset of the given polytopes such that each input point is covered by at least one polytope and the number of selected polytopes is minimal. By using epsilon-nets, we provide the first constant-factor approximation algorithm for this problem. The second set of problems that we consider are power assignment problems in wireless networks. Ad hoc wireless networks are a priori unstructured in a sense that they lack a predetermined interconnectivity. We consider a number of typical connectivity requirements and either give the first algorithms that compute a (1 + )-approximate energy efficient solution to them, or drastically improve upon existing algorithms in running time. The algorithms are based on coresets. We then extend the algorithms from the Euclidean case to metrics of bounded-doubling dimension and study metric spaces of bounded-doubling dimension more in-depth. The last problem that we consider is the k-hop minimum spanning tree, that is, we are given a graph and a specified root node and we would like to find a minimum spanning tree of the graph such that each root-leaf path contains at most k edges. We give the first PTAS for the problem in the Euclidean plane.