Theory and algorithm of multiflow, facility location, and network design

本研究的主要成果是完成了图G上多设施选址问题(最小0-扩张问题)在多项式时间可解的图的分类。在证明中，我们在一类图上引入了离散凸函数，开辟了新的研究方向“多流和设施选址的离散凸性”。这是朝着多流、设施选址和网络设计的统一理论迈出的重要一步，而这正是本研究项目的目标。

The main result of this research project is to complete the classification of graphs G for which multifacility location problem (minimum 0-extension problem) on G is polynomial time solvable. In the proof, we introduced discrete convex functions on a class of graphs, and opened up new research direction "discrete convexity for multiflow and facility locations." This is an important step toward a unified theory for multiflow, facility location, and network design, which was the goal of this research project.