A simple greedy approximation algorithm for the minimum connected \(k\) -Cente

详细信息    查看全文

• 作者：Dongyue Liang ; Liquan Mei ; James Willson ; Wei Wang
• 关键词：k ; Center ; Greedy algorithm ; Approximation algorithm
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1417-1429
• 全文大小：571 KB
• 参考文献：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
  Bondy JA, Murty SR (1976) Graph theory with applications. Elsevier Science Publishing Co., Inc., New YorkCrossRef MATH
  Chuzhoy J, Guha S, Halperin E, Khama S, Kortsarz G, Krauthgamer R, Naor J (2005) Asymmetric k-Center is \(\log ^* n\) hard to approximate. J ACM 52(4):538–551MathSciNet CrossRef MATH
  Dyer ME, Frieze AM (1985) A simple heuristic for the \(p\) -center problem. Oper Res Lett 3(6):285–288
  Ge R, Ester M, Gao BJ, Hu Z, Bhattacharya B, Ben-Moshe B (2008) Joint cluster analysis of attribute data and delationship data: the connected \(k\) -Center problem, algorithms and applications. ACM Trans Knowl Discov Data 2:7CrossRef
  Hochbaum DS, Shmoys DB (1985) A best possible heuristic for the \(k\) -center problem. Math Oper Res 10(2):180–184MathSciNet CrossRef MATH
  Khuller S, Sussmann YJ (2000) The capacitated \(K\) -Center problem. SIAM J Discrete Math 13(3):403–418MathSciNet CrossRef MATH
  Khuller S, Pless R, Sussmann YJ (2000) Fault tolerant \(K\) -center problems. Theor Comput Sci 242(1–2):237–245MathSciNet CrossRef MATH
  Panigrahy R, Vishwanathan S (1998) An \(O(log^{*}n)\) approximation algorithm for the asymmetric \(p\) -Center problem. J Algorithm 27:259–268MathSciNet CrossRef MATH
  Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, CambridgeCrossRef MATH
  
• 作者单位：Dongyue Liang (1)
  Liquan Mei (1)
  James Willson (2)
  Wei Wang (1)
  
  1. School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, 710049, People’s Republic of China
  2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

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 Ge et al. (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\).