Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9797
• 期：1
• 页码：222-234
• 全文大小：245 KB
• 参考文献：1.Alumur, S.A., Kara, B.Y.: Network hub location problems: the state of the art. Netw. Hub Location Probl.: State Art 190, 1–21 (2008)MathSciNet MATH
  2.Campbell, J.F.: Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res. 72, 387–405 (1994)CrossRef MATH
  3.Campbell, J.F., Ernst, A.T.: Hub location problems. In: Drezner, Z., Hamacher, H.W. (eds.) Facility Location: Applications and Theory, pp. 373–407. Springer, Berlin (2002)CrossRef
  4.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2009)MATH
  5.Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of STOC 2014, pp. 624–633 (2014)
  6.Ernst, A.T., Hamacher, H., Jiang, H., Krishnamoorthy, M., Woeginger, G.: Uncapacitated single and multiple allocation \(p\) -hub center problem. Comput. Oper. Res. 36, 2230–2241 (2009)MathSciNet CrossRef MATH
  7.Kara, B.Y., Tansel, B.Ç.: On the single-assignment \(p\) -hub center problem. Eur. J. Oper. Res. 125, 648–655 (2000)CrossRef MATH
  8.Liang, H.: The hardness and approximation of the star \(p\) -hub center problem. Oper. Res. Lett. 41, 138–141 (2013)MathSciNet CrossRef MATH
  9.Meyer, T., Ernst, A., Krishnamoorthy, M.: A 2-phase algorithm for solving the single allocation \(p\) -hub center problem. Comput. Oper. Res. 36, 3143–3151 (2009)CrossRef MATH
  10.O’Kelly, M.E., Miller, H.J.: Solution strategies for the single facility minimax hub location problem. Pap. Reg. Sci. 70, 376–380 (1991)
  11.Yaman, H., Elloumi, S.: Star \(p\) -hub center problem and star \(p\) -hub median problem with bounded path length. Comput. Oper. Res, 39, 2725–2732 (2012)MathSciNet CrossRef MATH
  
• 作者单位：Li-Hsuan Chen (15)
  Dun-Wei Cheng (16)
  Sun-Yuan Hsieh (16)
  Ling-Ju Hung (16)
  Chia-Wei Lee (16)
  Bang Ye Wu (15)
  
  15. Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, 62102, Taiwan
  16. Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, 701, Taiwan
  
• 丛书名：Computing and Combinatorics
• ISBN：978-3-319-42634-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9797

文摘

Given a metric graph \(G=(V, E, w)\) and a center \(c\in V\), and an integer k, the Star k-Hub Center Problem is to find a depth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. The Star k-Hub Center Problem is NP-hard. (Liang, Operations Research Letters, 2013) proved that for any \(\epsilon >0\), it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio \(1.25-\epsilon \). In the same paper, a 3.5-approximation algorithm was given for the Star k-Hub Center Problem. In this paper, we show that for any \(\epsilon > 0\), to approximate the Star k-Hub Center Problem to a ratio \(1.5 - \epsilon \) is NP-hard. Moreover, we give 2-approximation and \(\frac{5}{3}\)-approximation algorithms for the same problem.