We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the @math -median, @math -center and @math -means problems. All these problems admit natural local search heuristics: for example, in the UFL problem the natural moves are to open a new facility, close an existing facility, and to swap a closed facility for an open one; in @math -medians, we are allowed only swap moves. The local-search algorithm for @math -median was analyzed by (SIAM J. Comput. 33(3):544-562, 2004), who used a clever coupling'' argument to show that local optima had cost at most constant times the global optimum. They also used this argument to show that the local search algorithm for UFL was 3-approximation; their techniques have since been applied to other facility location problems. In this paper, we give a proof of the @math -median result which avoids this coupling argument. These arguments can be used in other settings where the arguments have been used. We also show that for the problem of opening @math facilities @math to minimize the objective function @math , the natural swap-based local-search algorithm is a @math -approximation. This implies constant-factor approximations for @math -medians (when @math ), and @math -means (when @math ), and an @math -approximation algorithm for the @math -center problem (which is essentially @math ).
Tight bounds for the @math -center problem are known: there is a @math -approximation algorithm due to @cite_18 @cite_10 , and this is tight unless @math .
@cite_18 @cite_10
2785893262 2293564405 2158196818 2105773506
The @math -center problem is a classical combinatorial optimization problem which asks to find @math centers such that the maximum distance of any input point in a set @math to its assigned center is minimized. The problem allows for elegant @math -approximations. However, the situation becomes significantly more difficult when constraints are added to the problem. We raise the question whether general methods can be derived to turn an approximation algorithm for a clustering problem with some constraints into an approximation algorithm that respects one constraint more. Our constraint of choice is privacy: Here, we are asked to only open a center when at least @math clients will be assigned to it. We show how to combine privacy with several other constraints. We consider the k-Center problem and some generalizations. For k-Center a set of kcenter vertices needs to be found in a graph G with edge lengths, such that the distance from any vertex ofi¾?G to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [ICALP 2011]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter k, and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameteri¾?h, but implies that such an algorithm must have at least doubly exponential running time in h if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor ofi¾?2 by combining the parameters k andi¾?h: we develop a fixed-parameter 3 2-approximation with running time @math . We also provide similar fixed-parameter approximations for the weightedk-Center and @math -Partition problems, which generalize k-Center. In this paper we study several instances of the alignedk-center problem where the goal is, given a set of points S in the plane and a parameter k ⩾ 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constrained version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, or a polygon. We first consider the simplest version of the problem where the line l is given in advance; we can solve this problem in time O(n log2 n). In the case where only the direction of l is fixed, we give an O(n2log2 n)-time algorithm. When l is an arbitrary line, we give a randomized algorithm with expected running time O(n4log2 n). Then we present (1+e)-approximation algorithms for these three problems. When we denote T(k, e) = (k e2+(k e) log k) log(1 e), these algorithms run in O(n log k + T(k, e)) time, O(n log k + T(k, e) e) time, and O(n log k + T(k, e) e2) time, respectively. For k = O(n1 3 log n), we also give randomized algorithms with expected running times O(n + (k e2) log(1 e)), O(n+(k e3) log(1 e)), and O(n + (k e4) log(1 e)), respectively. In the classic k-center problem, we are given a metric graph, and the objective is to open k nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of k-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: 1 We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version. 2 We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of 1+e. We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by 1+e.