CS787: Advanced AlgorithmsTopic: Local Search Algorithms Presenter(s): Theodora Hinkle, Ning ZhangIn this note, we will survey the local search heuristics for the metric k-median and facilitylocation problems. We define the locality gap of a local search heuristics for a minimizationproblem as the maximum ratio of local optimal solution (produced by local search heuristics) tothe global optimal solution. For k-median, the local search with single swap has a locality gap of 5.Moreover, if we allow p facilities to be swapped simultaneously, the locality gap will be 3+2p. For(uncapacitated) facility location, the local search, which permits adding, dropping, and swappinga facility, has a locality gap of 3. All above results are currently the best ones by using local searchheuristics.17.2.1 Introduction17.2.1.1 Background for k-median and facility location problemsFacility location problems capture a common need of many real world businesses: to decide whereto locate their facilities in a way that most effectively serves their clients. Many aspects of the realworld problem make finding solutions difficult, and even the simplified models of metric k-medianand metric uncapacitated facility location are hard problems.A facility location problem generally has a set of possible facility locations and a set of clients tobe served. There can be distances defined between the clients and facilities, leading to a measureof effectiveness of a solution can vary depending on the service cost, the distance between clientsand the facilities they are assigned to in the solution. There can also be unequal costs to openingdifferent facilities, leading to a measure of effectiveness depending on the facility cost, the totalcost to open the facilities chosen by a solution.Using various combinations of these two measures as objective functions to be minimized leads tointeresting problems. In metric k-median, the number of facilities which may be open is at mostk and the total service cost to all clients is minimized. In metric uncapacitated facility location,the sum of the total facility cost and service cost is minimized, and there are no restrictions on thenumber of clients any facility can serve. We will formally define these two problem shortly.17.2.1.2 Background for local search heuristicsLocal search is a metaheuristic for solving computationally hard optimization problems. Localsearch can be used on problems that can be formulated as finding a solution maximizing a criterionamong a number of candidate (feasible) solutions. Local search algorithms move from solution tosolution in the space of candidate solutions (the search space) until the local optimal solution isfound (or a time bound is elapsed). Now, the question is how local search algorithm starts from1a candidate solution and then iteratively moves to a better solution? This is only possible if aneighborhood relation is defined on the search space. As an example, the neighborhood of avertex cover could be defined as another vertex cover only differing by one node.Now, we define the local search algorithm (Algorithm 1) formally. A generic local search algorithmcan be described by a set S∗of all feasible solutions, a cost function c: S∗→ R, a neighborhoodstructure N: S∗→ 2S∗, and an oracle that, given any solution S, finds a solution S0∈ N (S)such that c(S0) < c(S). A solution S ∈ S∗is called local optimal if c(S) ≤ c(S0) for all S0∈N(S). For example, Algorithm 1 always returns the local optimal solution. The cost function andneighborhood structure N will be different for different problems and algorithms.Algorithm 1 Local Search Algorithm1: S is an arbitrary feasible solution in S∗2: while ∃S0∈ N(S) such that c(S0) < c(S) do3: S ← S04: end while5: return SFor an instance I of a minimization problem, let global(I) denote the cost of the global optimum andlocal(I) be the cost of a locally optimum solution provided by a certain local search heuristic. Wecall the supremum of the ratio local(I)/global(I) the locality gap of this local search procedure.Our proof of the locality gap proceeds by considering a suitable, polynomially large subset Q ⊆N(S) of neighboring solutions and arguing thatXS0∈Q(c(S0) − c(S)) ≤ α · c(O) − c(S)where O is the global optimal solution and α > 1 is a constant. This implies that c(S) ≤ α · c(O),which α gives the locality gap.17.2.2 Notations and Problem formulationIn the k-median and facility location problem, we are given two sets: F , the set of facilities, andC, the set of clients. Let cij≥ 0 denote the cost of serving client i ∈ C by a facility j ∈ F ; wewill think of this as the distance between client i and facility j. The goal in these problems isto identify a subset of facilities S ⊆ F and to serve all clients by facilities in S such that someobjective function is minimized. The facilities in S are said to be open. The metric versions ofthese problems assume that distances cijare symmetric and satisfy the triangle inequality. Theproblems considered in this paper are defined as follows.1. metric k-median problem: Given integer k, identify a set S ⊆ F of at most k facilities toopen such that the total cost of serving all clients by open facilities is minimized.22. metric uncapacitated facility location (UFL) problem: For reach facility i ∈ F , givena cost fi≥ 0 of opening facility i. The goal is to identify a set of facilities S ⊆ F such thatthe total cost of opening the facilities in S and serving all the clients by open facilities isminimized.17.2.3 k-median problem and analysis17.2.3.1 Local search with single swapIn this section, we consider a local search using single swap. A swap is effected by closing a facilitys ∈ S and opening a facility s0∈ F and is denoted by < s, s0>; hence the neighborhood of S isdefined as B(S) = {S − s + s0|s ∈ S}. We start with an arbitrary set of k facilities S and keepimproving the solution S with a single swap at a time until we reach a local optimal solution (wecan not improve the solution by a single swap). The algorithm is described in Algorithm 1.17.2.3.2 AnalysisLet S be the local optimal solution returned by the local search and O be a global optimal solution.We will show that this local search has a locality gap of 5, that is c(S) ≤ 5 · c(O). First, we useNS(s) to denote the set of clients that facility s serves in S and NO(o) to denote the set of clientsthat facility o serves in O. The