PROBLEM LINKAuthor: Hasan Jaddouh DIFFICULTYCHALLENGE PREREQUISITIESnone PROBLEMYou're given two $N\times N$ matrices $C$ and $D$. Construct a connected undirected graph on $N$ vertices while minimising its total cost. The cost of a graph with $M$ edges $(u_1,v_1),\dots,(u_M,v_M)$ and degrees of vertices $d_1,\dots,d_N$ is $$\sum_{i=1}^M C_{u_i,v_i} + \sum_{i=1}^N D_{i,d_i}\,.$$ Note that the vertex costs aren't necessarily increasing with increasing degrees. The test data are generated randomly. QUICK EXPLANATIONWhat, you want a quick explanation for an optimisation problem? Find a decent solution, then try adding/removing edges and hillclimbing. A decent solution is e.g. the minimum spanning tree or a graph with optimal degrees. EXPLANATIONFirst, let's list some statistical results.
One thing we can do easily is take a random solution  with $M$ edges and $N$ vertices, the cost is $~N\frac{H_{max}}{2}+M\frac{C_{max}}{2}$  and then try improving it by adding/removing edges (while keeping connectivity) and recalculating the cost; everytime if we find a better solution, we can keep improving that. Each improvement attempt runs in $O(N+M)$, but the limiting factor is just checking if it's still connected, so it can be done in $O(1)$ per failed attempt e.g. if the graph is a spanning tree ($M=N1$). It's usually a good idea to take less edges instead of many. We can also try improving a different solution than a random one. Minimum spanning treeNote that if the second sum didn't exist, we've got a problem that's wellknown and easy to solve: computing the MST of a complete graph. This can be done in $O(N^2)$ using a modification of JarnikPrim algorithm which uses a list instead of a heap. Turns out the expected cost of this tree is $~1.2C_{max}$. Of course, even if we find an MST, the second sum will give us $N$ random costs, so the expected costs of this approach is $~N\frac{H_{max}}{2}+1.2C_{max}$. Optimal degreesHow about optimising the second sum? We can just pick the minimum $H_{ij}$ for each $i$, but that doesn't guarantee us if there even is a connected graph with these degrees. Regardless, the expected minimum is $~H_{max}/N$, so their expected sum is $~H_{max}$ (instead of $H_{max}N/2$ for random choices). The required conditions for a connected graph with degrees $d_{1..N}$ are:
This works because we can just keep making edges between 2 vertices with the currently maximal $d_i$ and decrementing those $d_i$, which gives some graph with $\ge N1$ vertices; then we can keep removing a nonbridge edge from some component and using it to connect 2 components until the graph is connected. It might turn out that the degree sequence which gives the minimum cost from $H$ isn't feasible, but nonzero degrees are trivial, the expected $\sum d_i$ is $~N^2/2$ (the indices $j$ which give minima are random) so that condition shouldn't be a problem and if the parity doesn't fit, it can be fixed by changing just one degree. All in all, the cost of the second sum can be $~H_{max}$. We still need to choose edges to fit the degrees. This is good, because it allows us to minimise the cost of the first sum as far as possible and get something better than $~\frac{C_{max}}{2}\frac{N^2}{4}$ (there are $\sum d_i/2$ edges). After we choose the edges, we can still run the hillclimbing / random optimisation. Something elseWe have described two approaches which try to minimise one sum at the cost of keeping the other pretty large. Something in between would be even better  picking degrees so that the cost from $H$ wouldn't be toolarge and the number of edges wouldn't be too large either, choosing worse edges to get better degrees... it also depends on the specific values of $C_{max}$ and $H_{max}$. What did you use? AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 07 Oct '17, 19:32

vital part of problem is Minimum spanning tree.after that we have a network that all connected to each other ... now we can use add or remove(must remain connected!) some cable optimally for get best point....in this part we can use many approach for connect office optimally .. answered 16 Oct '17, 16:46
