Approximability results for the converse connected p-centre problem^†

† The abstract version of this paper was presented at the 38th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (38ACCMCC).

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,\ell )$ with a nonnegative edge length function ℓ, a vertex set $C\subset V$, and an integer p, $0<p<|V|$, let $d(v,C)$ denote the shortest distance from v to C of G for each vertex v in $V\setminus C$, and the eccentricity $ecc\left(C\right)$ of C denote $\underset{v\in V}{max}d(v,C)$. The connected p-centre problem is to find a vertex set P in V, $|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,\ell )$ and an integer $\gamma >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\left(P\right)\le \gamma$. 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|$, $ϵ>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|$, $ϵ>0$, for the converse connected p-centre problem unless $P=\mathrm{NP}$.

Keywords:

• combinatorial optimization
• computational complexity
• approximation algorithm
• NP-hard
• facility location with load balancing
• p-centre problem
• converse connected p-centre problem

2010 AMS Subject Classifications:

• 68Q25
• 68W40
• 68W25
• 68Q15
• 68Q17

Acknowledgments

We would like to thank the anonymous referees whose useful comments helped a lot to improve the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the author.

Notes

† The abstract version of this paper was presented at the 38th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing (38ACCMCC).

Additional information

Funding

This work was supported in part by the National Science Council of Taiwan under Contract NSC 102-2221-E-845-003 and MOST 103-2221-E-845-001.