Problem of the Week 795

The Hub-Choice is Yours

We missed a week because of fall break. So I am sending this one early. And besides, this is an instance of an NP-hard problem so probably you can use some extra time! The problem is a bit unusual, but I try to match problems to visiting speakers, so here goes.

Students who attended Jenny Ryan's talk on U S West's network problems might like to try their hand at the sort of problem the applied mathematicians at the phone company deal with.

Design a network with the following specifications. The prize goes to the student who achieves the lowest cost.

There are two types of points: hubs and customers. Your job is to select a set of hubs to be used, and an order in which to connect the hubs. Then fiber will we laid to accomplish two things:

Each customer will be connected to the nearest of the selected hubs.
The hubs will be connected to each other in a ring in the specified order (so that the breaking of an inter-hub connection will not affect communication; these inter-hub connections cannot go via a customer - they must be direct, hub-to-hub).
The cost of each hub is $500; thus the total hub-cost is 500*n where n is the number of hubs you select.
The cost per mile of fiber is $1000.00; the scale is 1 mile = 0.01 units.

The instructions for my students will include some comments telling them that I have a computer program that immediately spews out the cost of a selection, and I will be willing to answer two of their queries of that sort. Mathematica users can request the code from me: it spews out a nice picture of the network and total cost of a guess.

Example: If you choose {17, 20, 14, 13, 19}, then the inter-hub fiber goes from 17 to 20 to 14 to 13 to 19 and back to 17, and the total cost of the entire network works out to be $15,281.

Hub data

1    0.85    0.61
2    0.16    0.79
3    0.036   0.37
4    0.43    0.74
5    0.1     0.05
6    0.064   0.74
7    0.56    0.39
8    0.09    0.46
9    0.85    0.49
10   0.4     0.89
11   0.39    0.27
12   0.74    0.052
13   0.47    0.22
14   0.64    0.54
15   0.68    0.19
16   0.082   0.85
17   0.14    0.67
18   0.69    0.41
19   0.14    0.4
20   0.41    0.97
21   0.59    0.76
22   0.73    0.52
23   0.045   0.3
24   0.54    0.36
25   0.79    0.67
26   0.3     0.83
27   0.41    0.91
28   0.69    0.54
29   0.5     0.67
30   0.14    0.91

Customer data

1    0.67    0.058
2    0.72    0.46
3    0.89    0.17
4    0.78    0.29
5    0.64    0.86
6    0.7     0.87
7    0.14    0.65
8    0.54    0.46
9    0.81    0.6
10   0.83    0.57
11   0.98    0.46
12   0.63    0.69
13   0.54    0.9
14   0.26    0.35
15   0.45    0.72
16   0.86    0.065
17   0.047   0.63
18   0.066   0.92
19   0.058   0.16
20   0.35    0.3
21   0.12    0.45
22   0.5     0.69
23   0.77    0.36
24   0.011   0.82
25   0.87    0.71
26   0.093   0.79
27   0.77    0.34
28   0.32    0.56
29   0.28    0.81
30   0.12    0.77
31   0.96    0.44
32   0.17    0.45
33   0.71    0.19
34   0.81    0.098
35   0.51    0.49
36   0.56    0.18
37   1.      0.53
38   0.7     0.35
39   0.87    0.36
40   0.15    0.31
41   0.2     0.19
42   0.93    0.77
43   1.      0.72
44   0.18    0.79
45   0.26    0.74
46   0.97    0.72
47   0.74    0.96
48   0.18    0.7
49   0.66    0.89
50   0.66    0.32

Back to the Fall 1995 PotW Archive.

Jeff Erickson (jeffe@cs.berkeley.edu)
Last update: 06 Mar 96