若干组合优化问题的近似算法
文献类型：学位论文
| 作者 | 赵文波 |
| 学位类别 | 博士 |
| 答辩日期 | 2007-06-08 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 整数划分 路由 近似算法 组合优化 |
| 其他题名 | Approximation Algorithms for Several Combinatorial Optimization Problems |
| 中文摘要 | 大多数自然的组合优化问题，已经被证明是NP-hard。因此，在普遍相信的P≠NP的假设下，可以正确求解这些问题的任何算法，在最坏情况下都需要指数量级的时间，从而除规模很小的实例外，是不实用的。在这种情况下，近似算法作为克服这一困难的一种有效的方法受到了数学界和计算机界的极大关注。在这篇文章中，我们首先介绍一些关于近似算法的基本概念和基础知识，然后我们从近似算法的角度重点研究了以下两个组合优化问题： 1. k最小公共整数划分问题。给定k个正整数多重集X1,X2, …, Xk，我们的目标是找到一个元素个数最少的正整数多重集T使得对于每一个i，我们能把Xi的每一个元素划分成若干不相交的多重集使得它们的并集正好为T。这个问题在计算生物学上的ortholog assignment和DNA hybridization fingerprint assembly等问题中有着很重要的应用。 对于k>1，k最小公共整数划分问题已经被证明为NP-hard。在这篇文章中，我们给出了一个近似比为0.5625k的近似算法。我们的算法改进了前人的工作，是目前最好的近似算法。 2. 最小rooted star覆盖问题。给定一个长度限制D，一个完全无向图G = (V,E)以及关于图G上每一条边的距离函数l: E->Z^+，其中函数l满足三角不等式，图G中有一个顶点r被指定为root。我们的目标是找到数量最少的rooted star使得它们覆盖完图中的所有顶点且每一个rooted star的长度都不超过D。我们首先证明了这个问题是NP-hard，然后我们对这个问题给出了第一个常数近似比的近似算法。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 55 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6902]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 赵文波. 若干组合优化问题的近似算法[D]. 软件研究所. 中国科学院软件研究所. 2007. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。