Simple randomized algorithms for Connected Facility Location
Anupam Gupta

Abstract:

A slew of algorithms have been proposed recently for the Connected Facility Location problem, in which a set of
facilities have to be opened, and connected up by a Steiner tree. The cost of the solution comprises the cost of connecting the demands to the facilities, and M times the cost of the Steiner tree on the open facilities. This
problem, interesting in its own right also has applications to network design in the co-called "hose" model.

Constant factor approximation algorithms are now known for the problem via reductions to classical facility location [Karger Minkoff], LP rounding [GKKRY] and the primal dual schema [Swamy Kumar]. In this talk, we present a very simple randomized algorithm for the problem.