Algorithm Problem Classification

Question

There is great problem in one of the algo contest sites. I am trying to solve it for 5 days. I am not asking you to solve me this for me, as I am new to algorithms I would like to ask you help me with classification of this type problem, did anyone solved problems like this, what is the type of problem NP or not. Please do not think that I asking you to solve this for me, my purpose is just to learn algorithms and this is the problem which is enough difficult for me:

The goal of this puzzle is to determine where to place a set of gas stations so that they are closest to airports. Airports make use of a lot of gas for fueling planes, so placing gas stations close them is of strategical importance.

Input Specification Your program should take one and only one command line argument: the input file (passed in argv, args, arguments depending on the language). The input file is formatted as follows:

the first line contains an integer: n the number of airports the n following lines each contain 2 floating point values xi yi representing the coordinates of the ith airport the following line contains the number p of cases to analyze (p is always less than 5) the following p lines each contain one integer gi giving the number of required gas stations

Output Specifications: You program should output the result to the standard output (printf, print, echo, write): Your output should contain p lines, each line providing the gj coordinates xj,yj of the gas stations. Your solution score will be measured by the quality of the solution. The quality of the solution is measured by the total distance, the total distance D is the square root of the sum of squared distances from each airport to its closest gas station. The lower the total distance D, the higher your score will be.

Answer 1

This problem is the canonical unsupervised k-means classification problem. See here for the full details: http://en.wikipedia.org/wiki/K-means_clustering

For a quick hint (if you want to avoid complete spoilers) k-means simply starts by picking random locations for your gas stations. It improves the solution each iteration thereafter by reducing the cost of each individual gas station one at a time. It does this by moving a gas station with the goal of minimizing its cost for the set of airports that it currently fuels.