网络优化问题与经典组合最优化问题(如排序、装箱或背包问题)的组合型问题是近年来的研究热点之一。最短路和排序的组合型问题是指：寻找赋权有向图的一条路，将路上的边对应的工件放在并行机上处理，使得机器的最大完全时间尽可能地小。此问题目前最好的结果是一个2-近似算法，其主要思路是通过修改边的权重来避免选择权重过大的边。通过控制权重较大的边的条数，但不修改边的权重，我们得到了一个1.5-近似算法和一个多项式时间近似方案。 最短路和装箱的组合型问题是指：寻找赋权有向图的一条路，将路上的边对应的物品放入固定容量的箱子，使得所使用的箱子的个数尽可能地少。此问题是装箱问题的推广，不存在近似比小于1.5的多项式时间算法。目前最好的结果是一个1.75-近似算法，其主要思路是通过修改边的权重控制装入相同箱子的物品。通过控制权重较大的边的条数，但不修改边的权重，我们得到了一个1.5近似算法，这是最佳可能结果。