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.
# You are given a convex polygon P with n vertices, find out the radius of the *largest inscribed circle* in that polygon..
# You are given a list A of n points in the plane, find out the *minimum enclosing circle*.
# Given a number n, find out a placement of *n queens* on an nxn chessboard such that they don’t attack each other.
# Given n (n <= 1000) and S integers, find out a permutation p such that <tex>1 * p[1] + 2 * p[2] + .. + n * p[n] = S</tex>.
# 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 distances from the points in A to P is minimum.
# You are given a convex polygon P with n vertices, find out the radius of the largest inscribed circle in that polygon..
# You are given a list A of n points in the plane, find out the minimum enclosing circle.
# Given a number n, find out a placement of n queens on an nxn chessboard so that they don’t attack each other.
Given n and S integers, find out a permutation p such that 1 x p[1] + 2 x p[2] + .. + n x p[n] = S.
# 2n knights have to sit around a roundtable. Each knight is friends with n + 1 other knights. Find a seating arrangement such that each knight is placed between two friends.
# Given two line segments in 3d space find the minimum distance between them.
# A party of n people is too large and has to be split to two tables. Given that each of the people has at most three enemies in the group, find a seating arrangement such that each person sits at a table with at most one of his enemies.
# A party of n people is too large and has to be split to two tables. Given that each of the people has exactly three friends, find out a seating arrangement such that each person sits at a table where at least two other of his friends are seated.
# Given a set A of n black points and a set B of n white points (no three points are collinear), join each point in A with one point in B respectively such that no two segments will intersect.
# Given a set A with n points and a set B with m points, find a line that separates the two sets.
# Given two points A and B and a circle C, find a point D on C such that AD + DB is minimized.
