Finding maximum-cost minimum spanning trees

Summary form only given. Consider the scenario in which a start-up communication company charges its network users by the cost of the minimum spanning tree (MST) they use in their protocols. Wanting to increase their profits, they aim at maximizing the cost of the MST of their network. We consider two different cases. In the first case, the company has a set of links with fixed cost vector W and wants to configure the network so that the MST of the network has the maximum possible cost. In the second case, the network topology is fixed, but the costs on the links assume d different values W₁, W₂, ..., W_d over the day. The company wants to fix the link costs to a value W~ = Σ_i p_i w_i, for some weights p₁, p₂, ..., p_d where 0 ≤ p_i ≤ 1 and Σ_ip_i = 1, so that the resulting network has a maximum-cost MST.