利用可计算性与计算复杂性理论来研究组合最优化问题是近年来组合最优化、算法设计与计算复杂性分析研究者工作的重点和热点之一.由于组合最优化问题的数学模型来源于现实世界，有着深厚的应用背景，理论自有其深刻性.但由于组合最优化问题涉及面过广，至今还有许多问题没有被设计出有效的算法来加以解决，有些问题直到最近才引起研究者的关注.　　 本文从可计算性与计算复杂性理论、近似算法理论与组合最优化问题的联系入手，着重考虑了四类限制性的组合最优化问题，给出了一些有益的结果.文中大部分结果是作者与合作者的研究成果.　　 首先，我们根据现实应用背景定义了左时间窗口，讨论了带左时间窗口的四个组合最优化模型.我们设计了带左时间窗口的最短路问题的一个最优算法，给出了有向网络上顶点和弧、顶点带左时间窗口的中国邮递员问题的多项式时间算法以及无向图上顶点和边、顶点带左时间窗口的中国邮递员问题的弱渐近2一近似算法，提供了有向网络上弧带左时间窗口的中国邮递员问题的弱渐近最优算法，设计出了边带左时间窗口的货郎担问题的弱渐近2-近似算法，分析了带左时间窗口网络上的树划分问题的困难性，给出了特殊情形下这类问题的最优算法.其次，我们抽象出了四个限制性的星划分模型，并分析了它们各自的难易程度.再次，我们介绍了满足参数不等式的有向图上的货郎担问题，给出了一个max{1+γ31-γ2，+γ3/1-γ2}-近似算法，并证明了对于几乎所有的γ∈[1/2，1)，该近似算法比目前所知的任何一个近似方案都好.此外，我们考虑了三个具有最大竞争能力的选址模型和最小总费用人员分流问题，分析了它们的困难性，并设计算法给出了它们的启发式算法.最后，对上述工作进行了总结.