The minimum budgeted spanning tree problem is a problem situated at the intersection of the minimum spanning tree and the multi-knapsack problems. The minimum budgeted spanning tree problem is central in telecommunication and network design aeras, where the knapsack constraints may represent business constraints. In order to effectively solve the problem, we investigated a polyhedral analysis of the budgeted spanning tree problem. We provide several exact extended formulations for special cases of the problem. In the special case where exactly one knapsack constraint is involved, our approach builds upon a combination of matroid intersection and an application of the disjunctive programming. This extended formulation allows us to gain some insights on the structure of the problem. Moreover, by using the projection technique, the formulation could be exploited to generate valid inequalities that can be integrated in a Branch and Cut procedure.

This paper studies sequences of graphs satisfying the finite-time consensus property (i.e., iterating through such a finite sequence is equivalent to performing global or exact averaging) and their use in Gradient Tracking. We provide an explicit weight matrix representation of the studied sequences and prove their finite-time consensus property. Moreover, we incorporate the studied finite-time consensus topologies into Gradient Tracking and present a new algorithmic scheme called Gradient Tracking for Finite-Time Consensus Topologies (GT-FT). We analyze the new scheme for nonconvex problems with stochastic gradient estimates. Our analysis shows that the convergence rate of GT-FT does not depend on the heterogeneity of the agents' functions or the connectivity of any individual graph in the topology sequence. Furthermore, owing to the sparsity of the graphs, GT-FT requires lower communication costs than Gradient Tracking using the static counterpart of the topology sequence.