Assignment round one

Frequency Assignment

Problem

A mobile radio network assigns frequencies to its clients. If two clients are sufficiently close to each other, they must be assigned different frequencies. If they are far enough from each other they may share the frequency. Your task is to create an assignment that minimizes the number of frequencies used.

Assignment

Create a Java program that takes a graph representing a radio network and tries to find an optimal frequency assignment using some local search method.
HINT: Create first a local search method for the decision version: Is there a frequency assignment using only K frequencies. Then use it to make an iterative algorithm that starts with some high number of frequencies and tries to find frequency assignment with the local search. Then it should reduce the number of frequencies by one and (perhaps using the solution for previous level) tries to find a new assignment and repeat this until no better assignment is found.

Test your solution with two sets of similar instances: set 1 set 2. For each set, test how good solutions can be found in 1 minute and in 10 minutes.

Input

The program will be run with command

java Frequency <graph>

Output

The performance of the program will be evaluated by running it for a prespecified time and checking the best achieved solution. To assist this, each time the program finds a better assignment than before, it must print it out in the following format:
For each node n1, n2, an assignment in the format "n3 = 5;" ni = f; means that node ni uses frequency f, where f is a nonnegative integer.
Example output:

n1 = 0;
n2 = 2;
n3 = 1;

Deliverable

Return the commented source code and a small report describing your approach and results to schumach(at)tcs.hut.fi. Include your student number in the mail.

Grading

Correct solution on first try with sufficient report earns 3 points, each failed attempt decreasing points by 1. Submitted solutions are compared with each other and a reference solution. Good solutions are granted 1-2 extra points.

Example instances

Instance with 3 frequencies
Instance with 12 frequencies
Instance with 15 frequencies