Complexity analysis and algorithms for the Program Download Problem

详细信息    查看全文

• 作者：Chao Peng (1)
  Jie Zhou (2)
  Binhai Zhu (3)
  Hong Zhu (1)
  
  1. Software Engineering Institute ; East China Normal University ; 3663 Zhongshan North Road ; Shanghai ; 200062 ; China
  2. Mathematics and Science College ; Shanghai Normal University ; 100 Guilin Road ; Shanghai ; 200234 ; China
  3. Department of Computer Science ; Montana State University ; Bozeman ; MT ; 59717-3880 ; USA
  
• 关键词：Program Download Problem ; NP ; complete ; FPT algorithm ; Approximation algorithm
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：29
• 期：1
• 页码：216-227
• 全文大小：263 KB
• 参考文献：1. Aggarwal CC, Wolf JL, Yu PS (1996) A permutation-based pyramid broadcasting scheme for video-on-demand systems. In: Proceedings of the international conference on multimedia computing and systems, pp 118鈥?6
  2. Ahuja RK, Magnanti TL, Orlin JB (1993) Networks flows. Prentice-Hall, Englewood Cliffs
  3. Almeroth KC, Ammar MH (1996) The use of multicast delivery to provide a scalable and interactive video-on-demand service. IEEE J Sel Areas Commun 14(5):1110鈥?122 CrossRef
  4. Downey RG, Fellows MR (1999) Parameterized complexity. Springer, New York CrossRef
  5. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York
  6. Hua KA, Sheu S (1997) Skyscraper broadcasting: a new broadcasting scheme for metropolitan video-on-demand systems. In: Proceedings of the ACM SIGCOMM 鈥?7 conference, Cannes, pp 89鈥?00
  7. Inoue M, Ohnishi M, Peng C, Li R, Morino H (2011) NerveNet: a future regional platform network for various context-aware services with sensors and actuators. IEICE Trans Commun E94鈥揃(3):618鈥?29 CrossRef
  8. Juhn L, Tseng L (1997) Harmonic broadcasting for video-on-demand service. IEEE Trans Broadcast 43(3):268鈥?71 CrossRef
  9. Karagiannis G, Altintas O, Ekici E, Heijenk G, Jarupan B, Lin K, Weil T (2011) Vehicular networking: a survey and tutorial on requirements, architectures, challenges, standards and solutions. IEEE Commun Surv Tutor 13(4):584鈥?16 CrossRef
  10. Lu ZX, Shi Y, Wu WL, Fu B (2012) Efficient data retrieval scheduling for multi-channel wireless data broadcast. In: Proceedings of the 31st IEEE international conference on computer communications (INFOCOM), pp 891鈥?99
  11. Lu ZX, Wu WL, Fu B (2013) Optimal data retrieval scheduling in the multi-channel data broadcast environments. IEEE Trans Comput 62(12):2427鈥?439
  12. Papadimitriou CH (1994) Computational complexity. Addison-Wesley, New York
  13. Peng C, Shen H (2007) A new approximation algorithm for computing 2-restricted disjoint paths. IEICE Trans Inf Syst E90鈥揇(2):465鈥?72 CrossRef
  14. Peng C, Tan Y, Xiong NX, Yang LT, Park JH, Kim SS (2009) Adaptive video-on-demand broadcasting in ubiquitous computing environment. J Pers Ubiq Comput 13(7):479鈥?88 CrossRef
  15. Tovey CA (1984) A simplified NP-complete satisfiability problem. Discret Appl Math 8(1):85鈥?9 CrossRef
  16. Viswanathan S, Imielinski T (1996) Metropolitan area video-on-demand service using pyramid broadcasting. Multimed Syst 4(4):197鈥?08 CrossRef
  
• 刊物类别：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 Program Download Problem (PDP) which is to download a set of desired programs from multiple channels. When the problem is to decide whether the download can be done by a given deadline \(d\) and each program appears in each of the \(n\) channels at most once, denoted as \(\textit{PDP}(n,1,d)\) , we prove that \(\textit{PDP}(n,1,d)\) is NP-complete by a reduction from 3-SAT(3). We can extend the NP-hardness proof to \(\textit{PDP}(2,3,d)\) where there are only two channels but each program could appear in each channel at most 3 times, although \(\textit{PDP}(2,1,d)\) and \(\textit{PDP}(2,2,d)\) are both in P. We show that the aligned version of the problem (APDP) is polynomially solvable by reducing it to a maximum flow problem. For a different version of the problem, MPDP, where the objective is to maximize the number of program downloaded before a given deadline \(d\) , we prove that it is fixed-parameter tractable. Finally, we devise an approximation algorithm for \(\textit{MPDP}(2,p,d),\,p\ge 3\) , which aims to maximize the number of desired programs downloaded in two channels.