Approximate Submodularity in Network Design Problems
Journal Article
The paper “Approximate Submodularity in Network Design Problems” studies general network design problems where a firm strategically selects its network to better match supply and demand in the future. The paper observes that the arcs in network design problems are cover modular, i.e., approximately substitutes with each other, in the sense that local changes in the objective function can be used to bound global changes. The cover modularity is then applied to prove that a set of simple and intuitive heuristics achieve constant factor approximation guarantees in network design problems. Furthermore, the paper demonstrates cover modularity is also present in a general class of linear programming formulations.
Full Text
Duke Authors
Cited Authors
- DeValve, L; Pekeč, S; Wei, Y
Published Date
- November 28, 2022
Published In
Published By
Electronic International Standard Serial Number (EISSN)
- 1526-5463
International Standard Serial Number (ISSN)
- 0030-364X
Digital Object Identifier (DOI)
- 10.1287/opre.2022.2408
Language
- en