Imagine you are the head of the education department of a metropole like São Paulo, the biggest city in Brazil. The mayor commended a survey to evaluate how well the schools were distributed around the town. Not that well, sadly. There exist some empty terrains and the mayor wants to use this space to build new schools, but he is not sure of how many to build neither where the best locations are. Your task is to assign the construction sites of the new schools.

The schools should be positioned following two criteria:

- Every student must spend at most 30 minutes from home to the school.
- Every school should be close enough from security safe facilities, in the case of an emergency.

Based on these, your team created a map covering the city with disks of different radii. Each disk is centered at a security safe facility, and a person can move from any two points inside each disk in less than 30 minutes. Your task is now reduced to find the minimum number of construction sites such that each disk has at least one school on it. This problem is also known as the minimum *hit-set problem*. The mayor was impressed with your solution and started to say your name for the press.

It has been a while since your idea became public, but no solution has appeared yet. In fact, you discovered the problem is impossible to be solved in practical time (it is *NP-complete*). Even worst, you also discovered that it is hard to approximate (it is *W[1]-hard*). The clock is ticking and you should come up with a solution that runs in a reasonable amount of time (*running-time analysis*) and that assures you are not far away from the optimal solution (*quality analysis*).

In this post, we are going to focus on the quality analysis of the *local search algorithm* for solving the minimum hitting-set for disks in the plane.

## Local search

**General Minimization Problem**: From a set , find the subset that satisfies a property , i.e., , and also minimizes some function . In other words:

**Local Search**: It is a heuristic that can be used to approximate the solution of difficult optimization problems. Below is a general description of a -local search algorithm for the general minimization problem with .

**Input**: .

**Output**: .

- Let .
- For each -subset of .
- For each -subset of .
- Set .
- If .
- Set .
- Repeat.

- For each -subset of .

This naive -local search algorithm has complexity:

Quite bad, and we don’t even know how close from the optimal solution it would be the solution returned by the local search. Nonetheless, it is generally the case that one can exploit characteristics of the problem in order to improve its running time. In particular, there exists a 3-local search algorithm for the hitting-set problem with running-time complexity of [1]. No further comment on running-time will follow, and we are going to focus on the quality analysis from now on.

Besides running-time analysis, approximation algorithms must also be analyzed for its quality, which means to state how far is the solution returned by the algorithm from the optimal solution. For example, a 2-approximation algorithm for a minimization problem is guaranteed to return a solution that is at most twice the value of the optimal solution:

## Hitting-Set for disks in the plane

The input of the hitting-set problem are the sets and a collection of subsets . The function states if the chosen subset hits every set of the collection , i.e., every set has at least one element of on it.

We call the pair a *range space*. Take any two disjoint subsets . Consider a graph on vertices and such that for every in which and there exists at least one edge with and . If graph is bipartite and planar, the range space is said to satisfy the *locality condition*.

There are many range spaces that satisfy the locality condition. The range spaces formed by disks in the plane is one of them.

**Claim 1**: For a collection of disks in the plane and , it is possible to construct a bipartite planar graph in which the locality condition is true.

*Proof*: We are going to need some quick facts about Delaunay Triangulation. It will be useful to take a look at some material on Delaunay Triangulations and Voronoi Diagrams if you are not familiar with them before proceeding the reading.

Let and consider the Delaunay Triangulation of . Recall that the circumcircle of every triangle of DT has no other point of (*empty circle property*). I am going to use this fact to show that if two points forms an edge of DT then there exists a circle passing through and with no other point of in its interior.

Consider any two points and trace the median line of and as shown in the figure.

From all the circles passing through and , the one centered at is the smallest one. In particular, this circle is the one in which the diameter has the same length of the segment .

Suppose the edge . Moreover, assume that for every circle with and in its boundary there exists at least one other points of in its interior. Notice this is only possible if there exist points in the interior of the circle centered at , implying the following partial triangulation:

But this triangulation does not respect the empty circle property of the Delaunay Triangulation, and the edge cannot be part of DT. That is a contradiction.

It is easy to see that any collection of disks in the plane induces a connected graph on a Delaunay Triangulation. Assume there exists a collection of disks in which the induced graph is not connected. Take the smallest disk such that the induced graph is not connected and shrink the circle until there are two vertices in the boundary of the circle. If there is no other point of in the interior of the circle, the edge belongs to the Delaunay Triangulation and the graph is indeed connected. Otherwise, there exists a point in the interior of the circle. There are two possibilities: Or vertices are in different components or vertices are in different components. In either way, it is possible to shrink even more the circle in order to get another one with two points on its boundary and that also induces a disconnected graph. But this contradicts the first circle being the smallest one with the required property.

By the last result, any collection of disks induces a connected graph in a Delaunay Triangulation, implying that for every disk in which and there exists at least one edge such that and . To get a bipartite graph, we simply have to remove all the edges between pairs of vertices from and between pairs of points from .

The key idea in the quality analysis is to use the optimal set and the set returned by the -local search in order to construct the bipartite planar graph . The reader might be wondering why we assume sets and are disjoint. Indeed, they are not. But we are going to argue that this won’t matter for the analysis.

Assume, for one moment, that sets and are disjoint. Let and define the following sets:

The sets are disjoint. Further, assume there exists a constant such that

Notice that , as is the optimal solution. But this implies

Therefore, if we find the constant in which inequality (1) holds, we are able to guarantee that the -local search solution is not further than times the optimal solution.

## Quality Analysis

When the -local search finishes with solution , there exists no -subset and -subset such that satisfies property . There exists a bipartite planar graph by claim 1 (here, is the optimal set). Further, as a consequence of -local search, this graph has the ** -locality property**:

For every subset such that ,

where are the set of neighbors of the set .

**Theorem 1**: Let be a bipartite planar graph such that for every subset of size we have . Then, .

The proof is a little bit long, and just a sketch will be presented here. The full proof can be checked in the references.

From Euller’s formula for planar graphs:

where denotes the set of vertices of with degree and the set of vertices of with degree greater then . Then,

Therefore, in order to prove , it is enough to show that

In order to show the latter inequality, construct the auxiliar graph :

Assume the graph is -connected. The proof is also valid for the case in which is not, but it is a technicality that makes the proof harder to follow (more details in the references). Consider any embedding of the graph in the plane. Vertices of are identified as edges in and vertices of are drawn in the interior of faces of . Moreover, edges in can be single or double. An edge is a double edge if there exist vertices such that . Notice that it is not possible to have a triple edge, since that would mean graph would not have the -locality-property.

Some notation will be helpful. Let to denote a face of with edges in its boundary; a face with maximum number of double edges in its boundary is called a *full face*; and naturally define as the set of vertices of of degree 3 (single and double edges) in the interior (boundary) of face .

It is easy to see that the following claims are true.

**Claim 2**: For , let . Then . Further, a triangular face has no double edge.

**Claim 3**: For , let . Then .

**Claim 4**: For , let be a full face. If is even, then . If is odd then .

The key idea of the proof is to define a weight function for each face in the graph .

.

Extending this definition to the graph

By using claims 2-4, it is possible to show that (details in [3])

## Concluding Remarks

In fact, the quality analysis just shown can be used for every problem in which it is possible to construct the locality graph from any two disjoint subsets . In particular, the 4-local search heuristic also gives a 4-approximation algorithm for the following problems:

- Maximum independent set in the intersection graph of disks in the plane.
- Terrain guarding problem.
- Minimum dominating set in disk intersection graphs.
- Minimum dominating set in disk intersection graphs.
- Minimum set-cover for disks in the plane.

## Further Reading

**[1]** – **Bus**, Norbert; **Garg**, Shashwat; **Mustafa H.**, Nabil; **Ray**, Saurabh. Improved Local Search for Geometric Hitting Set.

**[2]** – **Bus**, Norbert; **Garg**, Shashwat; **Mustafa H.**, Nabil; **Ray**, Saurabh. Limits of Local Search: Quality and Efficiency.

**[3]** – **Antunes**, Daniel; **Mathieu**, Claire; **Mustafa H.**, Nabil. Combinatorics of Local Search: An Optimal 4-Local Hall’s Theorem for Planar Graphs.