Prepare for class discussion an answer to the following exercise. Due date: December 17, 2010.
Input: A set U of locations for n users, a set F of locations for m facilities and a distance matrix D=[dij] ∈ Rn× m.
Task: Select a set J ⊆ F of p locations where to install facilities such that the sum of the distances of each user to its closest installed facility is minimized, i.e.,
| min | ⎧ ⎨ ⎩ |
|
| dij | J ⊆ F and |J|=p | ⎫ ⎬ ⎭ |
Design construction heuristics and local search algorithms.
A possible application of local search to the GCP defines the following:
Show that any local optimum of this function corresponds to a feasible coloring. Does a global optimum correspond to a coloring that use the minimal possible number of colors?