网络设计（network design），理学-计算机科学技术-计算机科学理论-算法-近似算法，网络设计问题是同网络的连通性有关的一类组合优化问题的统称。这里的网络是指边或顶点上带有数的图。更常见的情况是边上带有数，边上的数一般可解释为边的长度、容量或权重。网络设计这个概念来自美国研究者M.R.加里（Michael Randolph Garey，1945-11-19～ ）和美国计算机科学家D.S.约翰逊（David Stifler Johnson，1945-12-09～2016-03-08）对NP困难问题的分类（见NP完全性）。但传统上多项式时间可解的许多优化问题，也可以归类到网络设计问题中。按照M.R.加里和D.S.约翰逊的分类，网络设计问题又包括五类子问题。①生成树问题。如最小生成树问题（见最小生成树）、斯坦纳树问题等。②割和连通性问题。如最小s-t割问题、最小割问题、多重割（multicut）问题、多路割（multiway cut）问题、最稀疏割（sparsest cut）问题、斯坦纳森林问题、斯坦纳网络问题等。③路由问题。如旅行售货商问题、中国邮递员问题等。④流问题。