A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

What is it about?

We consider the network design problem of Connected Submodular Maximization. Here we are given a graph, a submodular (i.e., 'diminishing returns') function defined on subsets of the graph vertices, and a value k. The goal is to select a size-k connected subgraph whose set of vertices has maximum value according to the submodular function. Our main result is an efficient algorithm for Connected Submodular Maximization that finds a solution that approximates the optimal solution to within a factor of eps^3/r^eps, where r is the graph radius of the optimal solution and eps is a chosen fixed value between 0 and 1.

Featured Image

Photo by BoliviaInteligente on Unsplash

Photo by BoliviaInteligente on Unsplash