TY - GEN
T1 - The program download problem
T2 - 19th International Computing and Combinatorics Conference, COCOON 2013
AU - Peng, Chao
AU - Zhou, Jie
AU - Zhu, Binhai
AU - Zhu, Hong
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Approximation Algorithm
KW - FPT Algorithm
KW - NP-Complete
KW - Program Download Problem
UR - https://www.scopus.com/pages/publications/84884965433
U2 - 10.1007/978-3-642-38768-5_61
DO - 10.1007/978-3-642-38768-5_61
M3 - 会议稿件
AN - SCOPUS:84884965433
SN - 9783642387678
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 688
EP - 696
BT - Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings
Y2 - 21 June 2013 through 21 June 2013
ER -