Approximation algorithms for the robust/soft-capacitated 2-level facility location problems

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately.