A ubiquitous network design problem in modern marketplaces is to choose a subset of available connections to allow match-making between supply and demand. An important special case from the operations literature is flexibility design (i.e., allocating subsets of limited resources to multiple demand classes), which we focus on as a motivating case. As a subset selection problem, flexibility design could benefit from the many existing approximation guarantees for submodular function maximization, except for the fact that the objective is well known to exhibit both submodular and supermodular behavior – which we illustrate with a simple example.

Despite this lack of submodularity, we observe that the objective function still maintains the critical property of submodular functions that allows deriving approximation guarantees for simple algorithms: local changes in the objective function can be used to bound global changes. By relaxing this equivalent definition of submodularity in an appropriate way, we define a new notion of approximately submodular functions, which we call cover-modular. We prove that the flexibility design problem possesses this structural property with a novel primal-dual analysis. We then use this structure to analyze a class of greedy heuristics and establish the first constant factor approximation guarantee for solving the general flexibility design problem. Further, we identify a significant practical byproduct of our primal-dual analysis: the dual solutions we construct can be used as surrogates to guide the heuristics, leading to order of magnitude gains in computational efficiency without loss of optimization performance. Finally, we extend our analysis by demonstrating the presence of cover modularity in a general class of linear programming formulations, indicating applicability of our approach to a wide range of network design problems distinct from flexibility design.