中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
若干组合优化问题的近似算法
作者: 赵文波
答辩日期: 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,然后我们对这个问题给出了第一个常数近似比的近似算法。
英文摘要: Most natural combinatorial optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conjecture that P ≠ NP, their exact solution is prohibitively time consuming. Coping with the intractability of these problems, via approximation algorithms, becomes a compelling subject of scientific inquiry in mathematics and computer science. In this article, we firstly introduce some basic concepts and knowledge about the approximation algorithm and then we study the following two NP-hard problems: 1. For the k-Minimum Common Integer Partition Problem, abbreviated as k-MCIP, we are given k multisets X1, ... , Xk of positive integers, the goal is to find an integer multiset T of the minimum size such that for every i, we can partition each of the integers in Xi so that the disjoint (multiset) union of their partitions equals T. This problem has applications in computational molecular biology, in particular, ortholog assignment and DNA hybridization fingerprint assembly. The problem is known to be NP-hard for any k > 1. In this article, We improve the approximation ratio for k-MCIP by viewing this problem as a flow decomposition problem in some flow network. We show an efficient 0.5625k-approximation algorithm, improving upon the previously best known 0.6139k-approximation algorithm for this problem. 2. For the minimum rooted star cover problem, we are given a complete graph G = (V, E) with a length function l: E->Z^+, that satisfies the triangle inequality, a designated root vertex r in V, and a length bound D, the objective is to find a minimum cardinality set of rooted stars, that covers all vertices in V such that the length of each rooted star is at most D, where a rooted star is a subset of E having a common center s and containing the edge (r, s). We show that this problem is NP-hard and we also present a constant ratio approximation algorithm for this problem.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6902
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200428015006002赵文波_paper.pdf(585KB)----限制开放-- 联系获取全文

Recommended Citation:
赵文波. 若干组合优化问题的近似算法[D]. 软件研究所. 中国科学院软件研究所. 2007-06-08.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[赵文波]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[赵文波]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace