Approximate Submodularity in Network Design Problems
Network design problems, such as flexibility design, are ubiquitous in modern marketplaces where firms constantly innovate new ways to match supply and demand. We develop a primal-dual based approach to analyze the flexibility design problem, and establish that the problem possesses a novel structural property. The property, which we call cover modularity, can be interpreted as an approximate form of submodularity in the sense that local changes in the objective function can be used to bound global changes. We 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. Furthermore, 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.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 3507 Strategy, management and organisational behaviour
- 1503 Business and Management
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 3507 Strategy, management and organisational behaviour
- 1503 Business and Management
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics