| 摘要: | 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. |
如有問題歡迎與系統管理員聯繫 
