A simple greedy approximation algorithm for the minimum connected \(k\)-center problem.

*(English)*Zbl 1347.90073Summary: In this paper, we consider the connected \(k\)-Center (\(CkC\)) problem, which can be seen as the classic \(k\)-Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. \(CkC\) was first introduced by R. Ge et al. [“Joint cluster analysis of attribute data and relationship data; the connected \(k\)-center problem, algorithms and applications”, ACM Trans. Knowl. Discov. Data 2, 7 (2008)], in which they showed the \(NP\)-completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an \(NP\)-hard problem. We first present a simple polynomial time greedy-based \(2\)-approximation algorithm for the relaxation of \(CkC\) – the \(CkC^*\). Further, we give a \(6\)-approximation algorithm for \(CkC\).

##### MSC:

90C27 | Combinatorial optimization |

90C59 | Approximation methods and heuristics in mathematical programming |

PDF
BibTeX
XML
Cite

\textit{D. Liang} et al., J. Comb. Optim. 31, No. 4, 1417--1429 (2016; Zbl 1347.90073)

Full Text:
DOI

##### References:

[1] | Archer A (2001) Two \(O(log^{*}k)\) approximation algorithms for the asymmetric \(k\)-Center problem. Integer programming and cambinatorial optimization. Lecture Notes in Computer Science 2081:1-14 · Zbl 1010.90513 |

[2] | Bondy JA, Murty SR (1976) Graph theory with applications. Elsevier Science Publishing Co., Inc., New York · Zbl 1226.05083 |

[3] | Chuzhoy, J; Guha, S; Halperin, E; Khama, S; Kortsarz, G; Krauthgamer, R; Naor, J, Asymmetric k-center is \(\log ^* n\) hard to approximate, J ACM, 52, 538-551, (2005) · Zbl 1323.68297 |

[4] | Dyer ME, Frieze AM (1985) A simple heuristic for the \(p\)-center problem. Oper Res Lett 3(6):285-288 · Zbl 0556.90019 |

[5] | Ge, R; Ester, M; Gao, BJ; Hu, Z; Bhattacharya, B; Ben-Moshe, B, Joint cluster analysis of attribute data and delationship data: the connected \(k\)-center problem, algorithms and applications, ACM Trans Knowl Discov Data, 2, 7, (2008) |

[6] | Hochbaum, DS; Shmoys, DB, A best possible heuristic for the \(k\)-center problem, Math Oper Res, 10, 180-184, (1985) · Zbl 0565.90015 |

[7] | Khuller, S; Sussmann, YJ, The capacitated \(K\)-center problem, SIAM J Discrete Math, 13, 403-418, (2000) · Zbl 0947.05073 |

[8] | Khuller, S; Pless, R; Sussmann, YJ, Fault tolerant \(K\)-center problems, Theor Comput Sci, 242, 237-245, (2000) · Zbl 0944.68141 |

[9] | Panigrahy, R; Vishwanathan, S, An \(O(log^{*}n)\) approximation algorithm for the asymmetric \(p\)-center problem, J Algorithm, 27, 259-268, (1998) · Zbl 0917.68201 |

[10] | Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, Cambridge · Zbl 1219.90004 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.