Online and Approximate Network Construction from Bounded Connectivity Constraints
The Network Construction problem, studied by Angluin et al., Hodosa et al., and others, asks for a minimum-cost network satisfying a set of connectivity constraints which specify subsets of the vertices in the network that have to form connected subgraphs. More formally, given a set V of vertices, construction costs for all possible edges between pairs of vertices from V, and a sequence S1,S2,…⊆V