在实际应用领域产生的许多组合优化问题,如工件的排序加工问题、旅行售货员问题、装箱问题和频道分配问题都是NP困难问题.对于这类问题,从数学的角度出发,需要考虑问题的模型,求解此问题.在P≠NP的假设被人们广泛地认可下,在多项式时间内寻找此类问题的精确解是不可行的.因此,设计这类问题的近似算法,已成为计算机科学和数学中学术探讨的一个无法抗拒的主题.该文研究了从实际应用中产生的两个组合优化问题:带频道负荷的频道分配问题和带拒绝的装箱问题.第二章讨论了一般网络的带频道负荷经束的频道分配问题.概括地说,该文的主要创新点有1.推广了顶点染色的概念.在给出的图模型基础上,定义并讨论了k-m限制多重染色.当其中的参数取不同的特定值时,k-m限制多重染色分别对应于图的顶点染色和顶点多重染色.并利用序列算法得到该染色的一些理论结果与相应的顶点染色和多重染色的有关结论.2.给出了求星图和树图的μ-定向最优解的多项式时间算法.首先找到星图的μ-定向最优解,而后利用动态规划思想,从树的最底层叶子开始,依次向上一层构造子树的μ-定向最优解.并利用固定优先选择的分配方案在多项式时间内找到了树的μ-定向最优解.3.利用线性规划的原始对偶互补松弛条件得到拒绝装箱问题的一个下界,进而给出了被装箱物品和被拒绝物品的性质.4.在经典装箱问题的首次适应算法和降序首次适应算法的基础上,设计了带拒绝装箱问题的近似算法;RFF算法和RDFF算法.