NOVEL GENERALIZATIONS AND ALGORITHMS FOR THE MAX-k-COVERAGE PROBLEM

In this thesis we consider the fundamental optimization problem known as the Max-k- Coverage problem and its generalizations. We first discuss the well-studied generalization to the problem of maximizing a monotone submodular function subject to a cardinality constraint and introduce a new primal-dual algorithm which achieves the optimal approximation factor of (1 − 1/e). While greedy algorithms have been known to achieve this approximation factor, our algorithms also provide a dual certificate which upper bounds the optimum value of an instance. This certificate may be used in practice to provide much stronger guarantees than the worst-case (1 − 1/e) approximation factor. We then introduce a novel generalization of the Max-k-Coverage problem known as the Monotone Coverage Utility Maximization (mcum) problem. Here, we are given a set of clients C and a set of facilities F in a metric space (F ∪ C, d), a positive integer k, and a radius parameter r. Each client v ∈ C is associated with a non-decreasing utility function fv : N → R≥0, and the objective is to locate centers S ⊆ F with |S| = k so as to maximize ∑v∈C fv(S ∩ Bv(r)), where Bv(r) is the ball of radius r around v. This general problem reduces to the special case Threshold Utility Maximization (thrum), where the fv’s are threshold step functions, that is, fv(a) = wv if a ≥ ℓv for some positive integer ℓv, and 0 otherwise. thrum, in turn, generalizes Max-k-Coverage problem by putting ℓv = 1 for all clients. On the other hand, even when all ℓv’s are 2, the problem is as hard as Densest-k- Subgraph. We circumvent this hardness by addressing the “soft” version of the problem, where the same center can be opened multiple times. In this realm, we give a 1 2 -approximation in the uniform case where all ℓv’s equal ℓ, which readily implies a Θ(1/ log k) approximation for the general problem. We also describe matching integrality gaps for the natural LP relaxations for both problems. Furthermore, we consider the thrum problem from a radius-dilation perspective. Here, we want to obtain a utility of opt, but allow the algorithm’s neighborhood to be dilated to αr for α ≥ 1, with α as small as possible. This problem becomes equivalent to the Fault- tolerant k-Supplier with Outliers (FkSO) problem. Our main result is a 3-approximation for FkSO in the uniform case where all ℓv = ℓ, which improves upon an 11-approximation described by Inamdar and Varadarajan in 2020