Approximate Submodularity in Network Design Problems

Date: February 23, 2023
Time: 4:00 pm
Room: DBH 4011
Speaker: Levi DeValve  
(University of Chicago)

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.


Levi DeValve is an assistant professor of Operations Management at the University of Chicago Booth School of Business. He earned his PhD in Decision Sciences at the Fuqua School of Business at Duke University in 2019, advised by Sasa Pekec and Yehua Wei. His research applies optimization techniques to improve performance in a variety of practical and complex operations problems, including assemble-to-order systems, inventory management, e-commerce fulfillment, and network design, and has been recognized with awards in the MSOM Practice-Based Research Competition and Service Science Paper Competition.

Close Menu
Skip to content