PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
The problem is, perhaps, one of the most well-studied NP-hard optimization problems. It is more commonly known as the metric “Facility Location” problem where the word metric is used to indicate the supply costs satisfy the triangle inequality. If the supply costs are not metric, then one can show that no polynomial-time algorithm can approximate the minimum cost within a factor o(log n) unless P = NP.
If one has the metric property, as was guaranteed in this month’s problem, then the optimum solution can be approximated within a constant factor. The first such algorithm was based on rounding the variables in a linear programming-based formulation of the problem and guaranteed the resulting solution cost no more than 3.16 times the optimum [1]. The first constant-factor approximation algorithm that did not rely on linear programming was a very simple “local search” algorithm. Given a solution, a “local step” is to try and close an open factory, open a closed factory, or swap an open factory with a closed factory. Once one of these is tried, reassign the stores to their nearest factory. If there is such a step that improves the cost, then take it. Otherwise, output the current solution. This very practical heuristic is known to produce a solution whose cost is, in the worst case, no more than 3 times the optimum cost. This has been analyzed in a few papers, but the simplest is in [2].
An alternative algorithm that produces a solution whose cost is within 3 times the optimum is found in [3]. The advantage here is that the algorithm is still easy to implement and has running time only O(m log m) where m = S*F. Modifications to this algorithm yield an algorithm that guarantees a solution of cost no more than 1.52 times the minimum cost, but the running time increases to O(n^3) where n = S+F [4]. There are many other heuristics I haven’t mentioned (the best is actually a 1.5-approximation); the point is that the problem is well studied and there are many easy to implement heuristics that run fast in practice and guarantee good solutions.
Many of the results cited here are also analyzed to be tight in that instances are given to show the heuristic performs almost as bad as the worst-case guarantee. The test data for this problem included many such bad examples. Also, for the interested, even metric facility location cannot be approximated better than roughly 1.463 unless every problem in NP can be solved with an algorithm whose running time is n^O(loglog n) [5]. This statement is stronger than P != NP, but is still an open question.
[1] J-H. Lin and J. Vitter, Approximation Algorithms for Geometric Median Problems.
[2] A. Gupta and K. Tangwongsan, Simpler Analysis of Local Search Algorithms for Facility Location
[3] K. Jain and V.V. Vazirani, Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation
[4] K. Jain, M. Mahdian, E. Markakis, A. Saberi and V.V. Vazirani, Approximation Algorithms for Facility Location via Dual Fitting with Factor-Revealing LP
[5] S. Guha and S. Khuller, Greedy Strikes Back: Improved Facility Location Algorithms