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

点击翻译按钮获取中文摘要

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.