Approximate Submodularity in Network Design Problems
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.
- DeValve, L; Pekeč, S; Wei, Y
- November 28, 2022
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)