TCO 2010 Marathon Match Round1 - Planarity

Problem

Given graph G=(V,E), the problem is to arrange the vertices of the graph so that number of intersecting pairs of edges is minimized.

Constraints

10 <= V <= 100

2V <= E <= 5V-1

all vertices are placed at distinct integral points within 700*700 square.

time limit: 10sec

memory limit: 1020MB

Submission 1 - 20.05 (297/361)

main idea: Assign all the vertices randomly and take best one.

The result was even worse than the arrangement of the Visualizer. but gained about 20 points in submission. Not so bad. It seems that it is possible to gain about 70 points without any clever work.

The most serious problem is that I don't like to compete zealously with this problem.

Example scores:
0) 68.0
1) 175.0
2) 15938.0
3) 3244.0
4) 8099.0
5) 465.0
6) 16960.0
7) 3344.0
8) 1843.0
9) 14379.0

Submission 2 - 50.22 (183/364)

main idea: Move each vertex u in V to center of its incident vertices. 

I was expecting to gain 70~80 points, but the result was very unsatisfying.

The second serious problem is that I can't estimate the leader's absolute score properly.

Example scores:
0) 52.0
1) 71.0
2) 5738.0
3) 862.0
4) 863.0
5) 132.0
6) 4345.0
7) 781.0
8) 372.0
9) 3846.0

Submission 3 - 56.25 (160/365)

main idea: Submission 2 + SA

Move outside vertex first.

Another unsatisfying result.

Example scores:
0) 48.0
1) 56.0
2) 5336.0
3) 809.0
4) 749.0
5) 99.0
6) 3848.0
7) 731.0
8) 370.0
9) 3558.0

I've found a bug somewhere in my code but I couldn't find it exactly yet

Submission 4 - 58.92(148/365)

Fixing the bug and tuning some redundant computation. I couldn't take another stride.

Moving a vertex to center of its incident vertices may not be a good approach. I think geometric median is better, but computing geometric median is very hard, complicated and, above all, time consuming.

I need a clever idea!

Example scores:
0) 49.0
1) 53.0
2) 5411.0
3) 808.0
4) 822.0
5) 83.0
6) 3887.0
7) 718.0
8) 323.0
9) 3579.0

Submission 5 - 62.45 (138/369)

2-Phase

Phase 1 - The same as the submission 4

Phase 2 - Check possible gains of the neighbor positions of center of mass. Take the most profitable position and move.

Example scores: 

0) 47.0
1) 52.0
2) 4862.0
3) 764.0
4) 704.0
5) 91.0
6) 3663.0
7) 643.0
8) 256.0
9) 3400.0

Submission 6 - 64.65 (136/376)

First 2 seconds - the same as the submission 4

Remaining time - Check possible gains of the neighbor position. Take most profitable position and move.

Example scores:
0) 47.0
1) 56.0
2) 4701.0
3) 694.0
4) 654.0
5) 111.0
6) 4938.0
7) 662.0
8) 265.0
9) 3166.0

Submission 7 - 66.13 (133/378)
Tuning some computations and parameters.
Allot 1 seconds for phase 1

It may be fruitful to consider using sweep line algorithm 

Example scores:
0) 44.0
1) 54.0
2) 4455.0
3) 697.0
4) 607.0
5) 98.0
6) 3507.0
7) 598.0
8) 242.0
9) 3270.0

Submission 8 - 71.00 (119/381)

Tuning some parameters.

Allot 0.5 seconds for phase 1

Restrict the size of the plain to 2/3*|E|

Phase 2.1 and 2.2 are most important.

I have to resolve statistical instabilities.

Example scores: 
0) 45.0
1) 50.0
2) 4435.0
3) 594.0
4) 598.0
5) 83.0
6) 4256.0
7) 589.0
8) 235.0
9) 3094.0

Submission 9 - 74.42 (93/383)

Replace checking intersection module with efficient one.

Restrict the number of iteration for phase1(center of mass method) 

Split phase2(search from neighbor) to several sub-phase

- Restrict the size of the plain to very little value((2V+E)/15)

- Double the size after 5.5sec

- Double the size again after 8.0sec

The method used in phase 1 "Center of Mass" is not good. using Sammon's mapping may be better.

Example scores:
0) 45.0
1) 47.0
2) 3563.0
3) 615.0
4) 568.0
5) 95.0
6) 2812.0
7) 526.0
8) 279.0
9) 2610.0

Submission 10 - 84.38 (44/392)

Fix neighbor search routine.

- search nearest neighbor first 

- select search direction randomly (It stifle the tendency of vertices to move in the same direction)

Tuning some parameters

The gap between my absolute score and leader's one may be very narrow.

Example scores:
0) 45.0
1) 42.0
2) 3529.0
3) 539.0
4) 547.0
5) 70.0
6) 2803.0
7) 537.0
8) 220.0
9) 2625.0

Submission 11 - 84.12 (49/407)

Adjust running time for each phase

Tuning some computation.

Restoring the best configuration after the end of each sub-phase doesn't seem to work.

Example scores:
0) 44.0
1) 39.0
2) 3893.0
3) 559.0
4) 584.0
5) 59.0
6) 2869.0
7) 504.0
8) 198.0
9) 2645.0

 

Submission 12 - 83.28 (50/407) 84.08->83.28

Use sammon mapping instead of center of mass.

Example scores:
0) 44.0
1) 43.0
2) 3591.0
3) 583.0
4) 563.0
5) 69.0
6) 2881.0
7) 537.0
8) 201.0
9) 2640.0

Submission 13 - 82.09 (58/416)

The last submission

Change time limit to 9.94sec

Example scores:
0) 44.0
1) 40.0
2) 3482.0
3) 560.0
4) 576.0
5) 71.0
6) 2896.0
7) 527.0
8) 228.0
9) 2771.0