Approximability results for the converse connected p-centre problem

University of Taipei > 理學院 > 資訊科學系 > 期刊論文 > Item 987654321/16015

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16015

题名:	Approximability results for the converse connected p-centre problem
作者:	Chen, Yen-Hung;陳彥宏
贡献者:	臺北市立大學資訊科學系
关键词:	combinatorial optimization;computational complexity;approximation algorithm;NP-hard;facility location with load balancing;p-centre problem;converse connected p-centre problem
日期:	2015-07
上传时间:	2017-07-31 13:51:19 (UTC+8)
摘要:	In this paper, we investigate a combinatorial optimization problem, called the converse connected p-centre problem which is the converse problem of the connected p-centre problem. This problem is a variant of the p-centre problem. Given an undirected graph G=(V,E,ℓ)G=(V,E,ℓ) with a nonnegative edge length function ℓ, a vertex set C⊂VC⊂V, and an integer p, 0<p<\|V\|0<p<\|V\|, let d(v,C)d(v,C) denote the shortest distance from v to C of G for each vertex v in V∖CV∖C, and the eccentricity ecc(C)ecc(C) of C denote maxv∈Vd(v,C)maxv∈Vd(v,C). The connected p-centre problem is to find a vertex set P in V, \|P\|=p\|P\|=p, such that the eccentricity of P is minimized but the induced subgraph of P must be connected. Given an undirected graph G=(V,E,ℓ)G=(V,E,ℓ) and an integer γ>0γ>0, the converse connected p-centre problem is to find a vertex set P in V with minimum cardinality such that the induced subgraph of P must be connected and the eccentricity ecc(P)≤γecc(P)≤γ. One of the applications of the converse connected p-centre problem has the facility location with load balancing and backup constraints. The connected p-centre problem had been shown to be NP-hard. However, it is still unclear whether there exists a polynomial time approximation algorithm for the converse connected p-centre problem. In this paper, we design the first approximation algorithm for the converse connected p-centre problem with approximation ratio of (1+ϵ)ln\|V\|(1+ϵ)ln⁡\|V\|, ϵ>0ϵ>0. We also discuss the approximation complexity for the converse connected p-centre problem. We show that there is no polynomial time approximation algorithm achieving an approximation ratio of (1−ϵ)ln\|V\|(1−ϵ)ln⁡\|V\|, ϵ>0ϵ>0, for the converse connected p-centre problem unless P=NPP=NP.
關聯:	International Journal of Computer Mathematics，P.1860-1868
显示于类别:	[資訊科學系] 期刊論文

文件中的档案:

没有与此文件相关的档案.

在uTaipei中所有的数据项都受到原著作权保护.

数据加载中.....