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:

  1. Every student must spend at most 30 minutes from home to the school.
  2. 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.

Continue reading

Advertisements

Conjugated Directions Methods – Part I

Let’s say we have the following unrestricted quadratic problem to solve:

\displaystyle \min_{x}{x^TQx - b^Tx} \quad \quad (P)

We further assume that Q \in \mathbb{R}^{n+1} is a symmetric positive definite matrix.

Let’s say that we have an iterative algorithm to find the solution x^\star of problem (P). The algorithm works by selecting a “good” direction d_k at iteration k and then walk some amount \alpha _k in that direction.

x_{k+1} = x_k + \alpha _k d_k.

Moreover, let’s say that we know how to compute \alpha _k in order to minimize the problem:

\displaystyle f(x_{k+1}) = \min_{\alpha _k}{f(x_k + \alpha _k d_k)}.

Continue reading