本论文系统地研究了排序（调度），装箱及其相关问题的多项式近似方案(approximationscheme)，其中重点考虑了以下两个问题:对于排序及其相关问题，目前已知的近似方案在运行时间上还可以进一步改进吗？该近似方案的思想还能进一步拓广并解决更多的相关问题吗？我们将在第二章探讨第一个问题。在第三四五章，我们会将近似方寨的设计思想推广到一系列的相关问题。　　在P≠NP猜想下，计算机领域的很多重要问题都不存在多项式时间精确算法，这一事实促使我们研究多项式时间下的近似算法。一般而言，近似算法主要通过以下两个指标来衡量:近似比(approximationratio)以及算法运行时间。前者衡量了最坏情况下算法返回的解与最优解之间的差距，而后者代表算法的计算效率。多项式时间近似方案(polynomialtimeapproximationscheme)是一系列多项式时间算法，它们的近似比无限接近于1，而运行时间则依赖于相应的近似程度。近似方案的存在意味着存在无限接近于最优算法的多项式时间近似算法，亦即存在多项式时间算法的序列，其近似比逐渐趋于1，而运行时间随着近似比的减小而增大。近似方案刻画了算法近似比与其运行时间之间的折衷(trade-off)，与此同时则导致了一个自然的问题，对于存在近似方案的问题而言，目前已知的近似方案在运行时间上是最好的吗？亦即，该近似方案下的折衷还能够被改进吗？我们将在第二章证明，在指数时间猜想(ExponentialTimeHypothesis，ETH)下，目前已知的关于排序问题的近似方案几乎都是最优的。　　接着我们考察排序问题的各种变体，这些交体都可以看成是在经典的排序模型上添加一些额外的约束构成的。我们试图刻画这些额外的约束是如何影响排序问题的。第三章我们将考察一类经典的约束-容量限制(cardinalityconstraints)，并且给出排序问题在容量限制下的近似方案，有意思的是，该近似方案的运行时间几乎与经典排序问题目前已知的最好的近似方案相同。更多其他类型的约束我们将在第5章考察。　　在上文所涉及到的排序及装箱问题中，问题的输入是在一开始就给定的，从这个意义上来说，它们也被叫做离线(offline)问题。与离线问题相对应的是在线(online)问题。在线问题中，输入不是一开始就全部给定，而是随着时间的推移逐步给出，而一个在线算法需要在任意时刻仅根据目前已知的信息给出问题当前时刻的解。与近似比相对应，我们用竞争比(competitiveratio)来衡量一个在线算法的优劣，该比值衡量了在任意时刻算法解与离线情况下的最优解之间的差距。由于未来信息的不确定性，即使最好的在线算法，其竞争比也往往不能达到1。竞争比近似方案(competitiveratioapproximationscheme)是一系列在线算法，其竞争比无限趋近于最优竞争比，而其运行时间则依赖于其竞争比。这是在线算法领域的一个新的概念，该近似方案提供了在线算法设计的一种系统的方法。在第四章中，我们将给出设计竞争比近似方案（竞争方案）的一种一般性的方法，利用该方法，我们将给出排序，装箱及其他相关问题的竞争方案。