大多数自然的组合优化问题，已经被证明是NP-hard。因此，在普遍相信的P≠NP的假设下，可以正确求解这些问题的任何算法，在最坏情况下都需要指数量级的时间，从而除规模很小的实例外，是不实用的。在这种情况下，近似算法作为克服这一困难的一种有效的方法受到了数学界和计算机界的极大关注。在这篇文章中，我们首先介绍一些关于近似算法的基本概念和基础知识，然后我们从近似算法的角度重点研究了以下两个组合优化问题：　　 1.k最小公共整数划分问题。给定k个正整数多重集Xl,…，Xk，我们的目标是找到一个元素个数最少的正整数多重集T使得对于每一个i，我们能把Xi的每一个元素划分成若干不相交的多重集使得它们的并集正好为T。这个问题在计算生物学上的ortholog assignment和DNA hybridization fingerprintassembly等问题中有着很重要的应用。对于k≥2，k最小公共整数划分问题已经被证明为NP-hard。在这篇文章中，我们给出了一个近似比为0.5625k的近似算法。我们的算法改进了前人的工作，是目前最好的近似算法。　　 2.最小rooted star覆盖问题。给定一个长度限制D，一个完全无向图G=(V,E)以及关于图G上每一条边的距离函数l:E→Z+，其中函数l满足三角不等式，图G中有一个顶点r∈V被指定为root。我们的目标是找到数量最少的rooted star使得它们覆盖完图中的所有顶点且每一个rooted star的长度都不超过D。我们首先证明了这个问题是NP-hard，然后我们对这个问题给出了第一个常数近似比的近似算法。