Here are a few problems that involve hill climbing or some form of local search. Feel free to suggest others and to discuss solutions.
 

# You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the *sum of square distances* from the points in A to P is minimum.
# You are given a list of A of n points with integer coordinates in the 3d plane. Find another point P(x, y) such that the *maximum of the Manhattan distances* from the points in A to P is minimum. (the manhattan distance between (x1, y1, z1) and (x2, y2, z2) is |x1 - x2| + |y1 - y2| + |z1 - z2|)
# You are given a list of A of n points with integer coordinates in the 2d plane. Find another point P(x, y) such that the *sum of euclidean distances* from the points in A to P is minimum.