Primal-dual algorithms for connected facility location problems (Q1884770): Difference between revisions

A Connected Facility Location problem (ConFL) generalizes FL-problems by additionally requiring the connectivity of the open facilities by a Steiner tree \(T\) yielding an extra cost of \(M\times\text{cost}(T)\); here \(M\) is an external factor due to the specific requirements for Steiner edges (f.e. connecting hubs). The authors propose constant factor approximation algorithms based on the primal-dual scheme, where simultaneously an integer primal solution and a solution of the dual of its linear programming relaxation are determined. In a first phase it is decided which facilities to open (by aggregating at least \(M\) demand) and which part of the cost should incurred to the Steiner tree portion of the dual solution. The second phase constructs a Steiner tree or an approximate one in polynomial time. Altogether, the paper shows certain constant factor approximations for ConFL as well as for the connected \(k\)-median problem (ConFL, where at most \(k\) facilities are allowed to open) and for special cases (f.e. \(M= 1\)).