The Program Download Problem: Complexity and Algorithms

详细信息    查看全文

• 作者：Chao Peng (18)
  Jie Zhou (18)
  Binhai Zhu (19)
  Hong Zhu (18)
  
• 关键词：Program Download Problem ; NP ; Complete ; FPT Algorithm ; Approximation Algorithm
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7936
• 期：1
• 页码：697-704
• 全文大小：165KB
• 参考文献：1. Almeroth, K.C., Ammar, M.H.: The use of multicast delivery to provide a scalable and interactive Video-on-Demand service. IEEE Journal on Selected Areas in Communications聽14(5), 1110鈥?122 (1996) CrossRef
  2. Viswanathan, S., Imielinski, T.: Metropolitan area Video-on-Demand service using pyramid broadcasting. Multimedia Systems聽4(4), 197鈥?08 (1996) CrossRef
  3. Peng, C., Tan, Y., Xiong, N.X., Yang, L.T., Park, J.H., Kim, S.S.: Adaptive Video-on-Demand Broadcasting in Ubiquitous Computing Environment. Journal of Personal and Ubiquitous Computing聽13(7), 479鈥?88 (2009) CrossRef
  4. Aggarwal, C.C., Wolf, J.L., Yu, P.S.: A permutation-based pyramid broadcasting scheme for Video-on-Demand systems. In: Proc. International Conference on Multimedia Computing and Systems, pp. 118鈥?26 (June 1996)
  5. Hua, K.A., Sheu, S.: Skyscraper broadcasting: a new broadcasting scheme for metropolitan Video-on-Demand systems. In: Proc. ACM SIGCOMM 1997 Conference, Cannes, France, pp. 89鈥?00 (September 1997)
  6. Juhn, L., Tseng, L.: Harmonic broadcasting for Video-on-Demand service. IEEE Trans. on Broadcasting聽43(3), 268鈥?71 (1997) CrossRef
  7. Inoue, M., Ohnishi, M., Peng, C., Li, R., Morino, H.: NerveNet: A Future Regional Platform Network for Various Context-Aware Services with Sensors and Actuators. IEICE Trans. on Communications聽E94-B(3), 618鈥?29 (2011) CrossRef
  8. Karagiannis, G., Altintas, O., Ekici, E., Heijenk, G., Jarupan, B., Lin, K., Weil, T.: Vehicular Networking: A Survey and Tutorial on Requirements, Architectures, Challenges, Standards and Solutions. IEEE Communications Surveys & Tutorials聽13(4), 584鈥?16 (2011) CrossRef
  9. Lu, Z.X., Shi, Y., Wu, W.L., Fu, B.: 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 (2012)
  10. Lu, Z.X., Wu, W.L., Fu, B.: Optimal Data Retrieval Scheduling in the Multi-Channel Data Broadcast Environments. IEEE Trans. on Computers (2012)
  11. Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Applied Mathematics聽8(1), 85鈥?9 (1984) CrossRef
  12. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, New York (1994)
  13. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Networks Flows. Prentice-Hall, NJ (1993)
  14. Peng, C., Shen, H.: A New Approximation Algorithm For Computing 2-Restricted Disjoint Paths. IEICE Transactions on Information and Systems聽E90-D(2), 465鈥?72 (2007) CrossRef
  15. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
  16. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)
  
• 作者单位：Chao Peng (18)
  Jie Zhou (18)
  Binhai Zhu (19)
  Hong Zhu (18)
  
  18. Software Engineering Institute, East China Normal University, 3663 Zhongshan North Rd., Shanghai, 200062, China
  19. Department of Computer Science, Montana State University, Bozeman, MT, 59717-3880, USA
  
• ISSN：1611-3349

文摘

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 PDP(n,1,d), we prove that PDP(n,1,d) is NP-Complete by a reduction from 3-SAT(3). We can extend the NP-hardness proof to PDP(2,2,d) where there are only two channels but each program could appear in each channel at most twice. 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.