Approximability results for the converse connected p-centre problem

uTaipei > College of Science > Department of Computer Science > Periodical Articles > Item 987654321/16015

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16015

Title:	Approximability results for the converse connected p-centre problem
Authors:	Chen, Yen-Hung;陳彥宏
Contributors:	臺北市立大學資訊科學系
Keywords:	combinatorial optimization;computational complexity;approximation algorithm;NP-hard;facility location with load balancing;p-centre problem;converse connected p-centre problem
Date:	2015-07
Issue Date:	2017-07-31 13:51:19 (UTC+8)
Abstract:	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.
Relation:	International Journal of Computer Mathematics，P.1860-1868
Appears in Collections:	[Department of Computer Science] Periodical Articles

Files in This Item:

There are no files associated with this item.

Loading...