兰州大学机构库 >数学与统计学院
关于一些网络最优化问题的近似算法的研究
Alternative TitleStudy on Approximations for Some Network Optimization Problems
李宪越
Thesis Advisor张和平 ; 堵丁柱
2009-11-24
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
Keyword斯坦纳树 连通控制集 单位圆盘图 单位圆球图 近似算法 近似比 多项式时间的近似模式
Abstract随着网络和网络技术的高速发展, 很多网络上的最优化问题被提出. 不幸的是, 很多这些问题都被证明是NP-完备问题.这就意味着, 目前这些问题不可能在多项式时间内得到最优解. 因此, 研究者们就致力于寻找这些NP-完备问题的近似算法. 本文主要研究了斯坦纳树问题和连通控制集问题及它们变形的近似算法. 这些问题都是网络中经典的最优化问题, 同时也是经典的NP-完备问题. 特别地, 在单位圆盘图上, 这些问题依然是NP-完备的. 对于这些问题, 我们都给出了近似算法, 并对算法进行了理论分析, 给出了算法的近似比. 本文共分为三章. 第一章首先介绍了图论中的一些基本概念和记号. 然后, 介绍了计算复杂度理论的一些基本概念. 接下来, 我们给出了近似算法的基本概念, 并通过顶点覆盖问题和它的一个的近似算法为例, 对其中的一些概念进行了解释. 最后, 罗列了本文得到的主要结论. 第二章主要研究了斯坦纳树问题的变形的近似算法. 给定一个边赋权图$G=(V,E)$和边权函数$c$, 及terminal集$X\subseteq V$, 斯坦纳树问题的目标是寻找一棵权重最小且连接termianl集中所有顶点的树. 斯坦纳树问题是一个经典的最优化问题和NP-完备问题. 在本章的开始, 我们将介绍斯坦纳树问题并综述其研究进展. 在第二章的第二节, 我们研究了一个斯坦纳树问题的变形, selected-internal 斯坦纳树问题. 给定一个边赋权完全图$G=(V,E)$和边权函数$c$, 及两个子集$X^{'}\subsetneq X\subseteq V$满足$|X-X^{'}|\geq 2$, selected-internal 斯坦纳树问题是在图$G$中寻找一棵最小的子树$T$连接$X$中的所有顶点,并且$X'$中的所有顶点均不是$T$的叶子节点. 假设$c$是度量函数, 本节得到了此问题的一个近似比为$(1+\rho)$的近似算法, 在这里$\rho$是目前为止斯坦纳树问题最好的近似比. 对于给定的一个顶点赋权图$G=(V,E)$和顶点赋权函数$w$, 及terminal集$X\subseteq V$, 顶点赋权斯坦纳树问题的目标是寻找一棵总权重最小且连接所有termianl集中顶点的树. 我们将在第二章余下的内容中在单位圆盘图上研究这个问题. 在第三节, 首先利用支撑树方法, 本文得到了一个近似比为5的近似算法. 然后, 通过将权重从顶点转移到边, 给出了一个近似比为$2.5\rho$的近似算法. 最后, 假设terminal集是$c$-local的, 我们证明了单位圆盘图上的顶点赋权斯坦纳树问题存在多项式时间的近似模式. 也就是说, 对于任意的$\varepsilon>0$, 总存在一个近似算法满足其近似比为1+$\varepsilon$. 第三章将研究单位圆盘图上的连通控制集问题. 给定图$G=(V,E)$, 称顶点子集$C\subseteq V$是一个连通控制集, 如果:1)对于任意的顶点$v\in V-C$, $v$总存在邻点在$C$中; 2)导出子图$G[C]$是连通的. 连通控制集问题的目标是寻找图$G$中一个包含顶点个数最少的连通控制集. 本章的第一节首先介绍了这个问题的背景及研究进展. 然后, 给出了计算连通控制集的基本思路. 在下一节中, 我们考查了极大独立集(MIS)与最小连通控制集的关系. 由于每个MIS都是控制集且可在多项式时间内得到, 因此研究者们经常通过寻找MIS并连接它们来得到一个连通控制集. 所以, MIS的大小与...
Other AbstractAs the highly developing of networks and network technique, a lot of network optimization problems are posed. Unfortunately, some of these problems are showed as NP-Complete problems. It implies that these problems can not be solved in polynomial-time. Hence, researchers focus on the approximation algorithms on these NP-Complete problems. In this thesis, we mainly study the approximation algorithm on Steiner tree problem and connected dominating set problem and their variants. These problems are classical network optimization problems and classical NP-Complete problems, even on the unit disk graphs. For all these problems, we present approximation algorithms. And then we give the theoretical analysis and obtain their approximation ratios. This thesis consists of three chapters. In chapter 1, we first introduce some basic concepts and notations of graph theory. Then some basic concepts of theory of computational complexity are introduced. Next, we present some concepts of approximation algorithm and use the vertex cover problem and a approximation algorithm of it as an example to explain some concepts. Finally, we list the main results in the thesis. Some approximation algorithms on variants of Steiner tree problem are studied in the second chapter. Given an edge-weighted graph $G=(V,E)$ with edge-weighted function $c$ and the terminal set $X\subseteq V$, Steiner tree problem is to find a minimum subgraph of $G$ interconnecting $X$. Steiner tree problem is a classical optimization problem and NP-Complete problem. At the beginning of this chapter, we introduce the Steiner tree problem and survey the research development of it. In the second section of chapter 2, we study the selected-internal Steiner tree problem, a variant of Steiner tree problem. Given an edge-weighted complete graph $G=(V,E)$ with edge-weighted function $c$, and two subsets $X^{'}\subseteq X\subseteq V$ with $|X-X^{'}|\geq 2$, selected-internal Steiner tree problem is to find a minimum subtree $T$ of $G$ interconnecting $X$ such that any leaf of $T$ does not belong to $X^{'}$. Suppose $c$ is metric, a $(1+\rho)$-approximation algorithm are presented in this section, where $\rho$ is the best-known approximation ratio for the Steiner tree problem. Given a node-weighted graph $G=(V,E)$ with node-weighted function $w: V \rightarrow R^+$ and the terminal set $X \subseteq V$, node-weighted Steiner tree problem is to find a minimum total weighted tree interconnecting all vertices in $X...
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225323
Collection数学与统计学院
Recommended Citation
GB/T 7714
李宪越. 关于一些网络最优化问题的近似算法的研究[D]. 兰州. 兰州大学,2009.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[李宪越]'s Articles
Baidu academic
Similar articles in Baidu academic
[李宪越]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[李宪越]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.