We consider a class of network-design problems with minimum sum of modification and network costs for minimum spanning trees under Hamming distance. By constructing three auxiliary networks, we present a strongly polynomial-time algorithm for this problem. The method can be applied to solve many network-design problems. And, we show that a variation model of this problem is NP-hard, even when the underlying network is a tree, by transforming the 0–1 knapsack problem to this model.

In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logistics optimization problems related to the optimal tree structures in a network. We show that the most optimal subtree problem is NP-hard by transforming the connected dominating set problem into this model. By constructing the network models of the most balanced spanning tree problem with edge set restrictions, and by finding the optimal subtrees in special networks, we present efficient computational methods for solving some logistics problems.

We propose a new primal-dual interior-point algorithm based on a new kernel function for linear optimization problems. New search directions and proximity functions are proposed based on the kernel function. We show that the new algorithm has and iteration bounds for large-update and small-update methods, respectively, which are currently the best known bounds for such methods.