4-Local Search gives a 4-approximation algorithm to the Geometric Hitting Set Problem

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 in 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 $U$ , find the subset $O \subseteq U$ that satisfies a property $P$ , i.e., $P(O)=\text{True}$ , and also minimizes some function $f:2^{U} \rightarrow \mathcal{R}$ . In other words:

$\displaystyle O = arg\min_{P(X)=\text{True}} f(X).$

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 $k$ -local search algorithm for the general minimization problem with $f(X) = |X|$ .

Input: $U$ .
Output: $S \in U$ .

Let $S=U$ .
For each -subset of .
1. For each -subset of .
  1. Set $S^\prime = S\setminus S^{-} \cup S^{+}$ .
  2. If .
    1. Set $S = S^\prime$ .
    2. Repeat.

This naive $k$ -local search algorithm has complexity:

$\displaystyle \binom{n}{k} \cdot \binom{n}{k-1} \cdot n \in O(n^{2k}).$

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 $\tilde{O}(n^{7/3})$ [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 the solution returned by the algorithm is 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:

$\displaystyle F(S) \leq 2 \cdot F(O).$

Hitting-Set for disks in the plane

The input of the hitting-set problem are the set $U=\mathcal{R}^2$ and a collection $\mathcal{D}$ of subsets of $U$ . The function $f(S)$ states if the chosen subset $S \subseteq U$ hits every set of $\mathcal{D}$ , i.e., every set $D \in \mathcal{D}$ has at least one element of $S$ on it.

We call the pair $\{U,\mathcal{D}\}$ a range space. Take any two disjoint subsets $R,B \subset U$ . Consider a graph $G$ on vertices $R$ and $B$ such that for every $D \in \mathcal{D}$ in which $D \cap R \neq \emptyset$ and $D \cap B \neq \emptyset$ there exists at least one edge $\{r,b\}$ with $r \in R$ and $b \in B$ . If graph $G(B,R,E)$ is bipartite and planar, the range space $\{U,\mathcal{D}\}$ 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.

Theorem 1: For a collection of disks $\mathcal{D}$ in the plane and any disjoint sets $R,B \subset \mathcal{R}^2$ , it is always possible to construct a graph $G(B,R,E)$ which respects the locality condition.

In order to proof theorem 1 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.

Delaunay Triangulation and Voronoi Diagram are duals.

Let $V = B \cup R$ and consider its Delaunay Triangulation $DT(V)$ .

Fact 1 (empty circle property): The circle defined by any three points of $V$ contains no other point of $V$ .

Claim 1: Any collection of disks $\mathcal{D}$ in the plane induces a connected graph on a Delaunay Triangulation $DT(V)$ .

Proof:

Assume there exists a collection of disks in which the induced graph is not connected. Take the smallest disk $D \in \mathcal{D}$ such that the induced graph is not connected and shrink the circle until there are two vertices $r,b$ belonging to different connected components. Such vertices must be in the boundary of the circle, otherwise one could shrink it until that condition is true. If there is no other point of $U$ in the interior of the circle, the edge $\{r,b\}$ belongs to the Delaunay Triangulation and the graph is indeed connected. Otherwise, there exists a point $w \in V$ in the interior of the circle. There are two possibilities: Or vertices $r,w$ are in different components or vertices $b,w$ 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 $\blacksquare$

We are now ready to prove theorem 1!

Proof:

Set the graph $H(B,R,E')$ as the Delaunay Triangulation of $B \cup R$ . Take any disk $D \in \mathcal{D}$ with $D \cap B \neq \emptyset$ and $D \cap R \neq \emptyset$ . By claim 1, the induced graph by $D$ in $H$ is connected and we have that there exists at least one edge $\{ u ,v \} \in E'$ with $u \in D \cap B$ and $v \in D \cap R$ . Finally, we set $G(B,R,E)$ as the graph $H$ without its non blue-red edges. Graph $G$ is bipartite, planar and respects the locality condition $\blacksquare$

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

Assume, for one moment, that sets $O$ and $S$ are not disjoint. Let $I = S \cap O$ and define the following sets:

$S^\prime = S \setminus I, \qquad O^\prime = O \setminus I.$

The sets $S^\prime,O^\prime$ are disjoint. Further, assume there exists a constant $C$ such that

$|S^\prime| \leq C \cdot|O^\prime|.\qquad \qquad (1)$

Notice that $C \geq 1$ , as $O$ is the optimal solution. But this implies

$\begin{array}{rl} |S^\prime| + |I| &\leq C \cdot |O^\prime| + |I| + \leq C \cdot |O^\prime| + C\cdot |I|\\[0.2in] |S| & \leq C \cdot |O|. \end{array}$

Therefore, if we find an expression for the disjoint sets $S',O'$ such expression is still valid for $S,O$ .

Quality Analysis

When the $k$ -local search finishes with solution $S$ , there exists no $k$ -subset $S^- \subset S$ and $(k-1)$ -subset $S^+ \subset U$ such that $(S \setminus S^-\cup S^+)$ satisfies property $P$ . By theorem 1, there exists a bipartite planar graph $G(S,O,E)$ (here, $O$ is the optimal set). As a consequence of $k$ -local search, this graph has the $k$ -locality property:

where $NG(S^\prime) \subset O$ are the set of neighbors of the set $S^\prime$ .

Theorem 2: Let $G(B,R,E)$ be a bipartite planar graph such that for every subset $B^\prime \subset B$ of size $|B^\prime| \leq 4$ we have $|NG(B^\prime)| \geq |B^\prime|$ . Then, $|B| \leq 4|R|$ .

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:

$\begin{array}{rl} |E| &\leq 2|V|\\[0.2in] \displaystyle 2\cdot |B_{=2}| + 3 \cdot |B_{=3}| + 4 \cdot |B_{\geq4}| \leq \sum_{i}{i|B_{=i}|} &\leq \displaystyle 2 \cdot \left( |R| + |B| \right), \end{array}$

where $B_{=i}$ denotes the set of vertices of $B$ with degree $i$ and $B_{\geq i}$ the set of vertices of $B$ with degree greater then $i$ . Then,

$\displaystyle |B_{\geq 4}| \leq |R| - \frac{|B_{=3}|}{2}.$

Therefore, in order to prove $|B| \leq 4|R|$ , it is enough to show that

$\begin{array}{rl} |B| &\leq 4|R|\\[0.2in] \displaystyle |B_{=2}| + |B_{=3}| + |B_{\geq4}| \leq |B_{=2}| + \frac{|B_{=3}|}{2} + |R| &\leq 4|R|\\[0.2in] \displaystyle |B_{=2}| + \frac{|B_{=3}|}{2} & \displaystyle \leq 3|R|. \end{array}$

In order to show the latter inequality, construct the auxiliar graph $H(R,\hat{E})$ :

$\displaystyle \hat{E} = \left\{ \: \{r_1,r_2\} \: \vert \: \exists b \in B \text{ such that } \{b,r_1\}, \{b,r_2\} \in E \right\}$

Assume the graph $H$ is $2$ -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 $H$ in the plane. Vertices of $B_{=2}$ are identified as edges in $H$ and vertices of $B_{=3}$ are drawn in the interior of faces of $H$ . Moreover, edges in $H$ can be single or double. An edge $\{r_1,r_2\} \in \hat{E}$ is a double edge if there exist vertices $b_1,b_2 \in B$ such that $\{b_1,r_1\},\{b_1,r_2\},\{b_2,r_1\},\{b_2,r_2\} \in E$ . Notice that it is not possible to have a triple edge, since that would mean graph $G$ would not have the $4$ -locality-property.

Some notation will be helpful. Let $F_i$ to denote a face of $H$ with $i$ edges in its boundary; a face with maximum number of double edges in its boundary is called a full face; and naturally define $B_{=3}^f (E_1^f,E_2^f)$ as the set of vertices of $B$ of degree 3 (single and double edges) in the interior (boundary) of face $f$ .

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

Claim 2: For $i\geq 4$ , let $f \in F_i$ . Then $|E_2^f| \leq \frac{i}{2}$ . Further, a triangular face has no double edge.

Claim 3: For $i \geq 4$ , let $f \in F_i$ . Then $|B_{=3}^f|\leq (i-2)$ .

Claim 4: For $i \geq 4$ , let $f \in F_i$ be a full face. If $i$ is even, then $|B_{=3}^f | \leq (i-4)$ . If $i$ is odd then $|B_{=3}^f| \leq (i-3)$ .

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

$\displaystyle w(f) = \frac{|E_{1}^f|}{2} +|E_{2}^f| + \frac{|B_{=3}^f|}{2}$ .

Extending this definition to the graph $H$

$\begin{array}{rl} \displaystyle w(H) = \sum_{f \in F} w(f) &= \displaystyle |E_1| + 2|E_2| + \frac{|B_{=3}^f|}{2}\\[0.2in] &= \displaystyle |B_{=2}| + \frac{|B_{=3}^f|}{2}. \end{array}$

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

$w(H) \leq 3|R|.$

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 $G(B,R,E)$ from any two disjoint subsets $B,R \subset U$ . 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 set-cover for disks in the plane.

4-Local Search gives a 4-approximation algorithm to the Geometric Hitting Set Problem

Local search

Hitting-Set for disks in the plane

Quality Analysis

Concluding Remarks

Further Reading

One thought on “4-Local Search gives a 4-approximation algorithm to the Geometric Hitting Set Problem”

Leave a comment Cancel reply

Published by Daniel Martins Antunes

Local search

Hitting-Set for disks in the plane

Quality Analysis

Concluding Remarks

Further Reading

Partager :

One thought on “4-Local Search gives a 4-approximation algorithm to the Geometric Hitting Set Problem”

Leave a comment Cancel reply

Published by Daniel Martins Antunes