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.