Complexity analysis and algorithms for the Program Download Problem

摘要

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, 3, d) where there are only two channels but each program could appear in each channel at most 3 times, although PDP(2, 1, d) and 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 MPDP(2, p, d), p >= 3, which aims to maximize the number of desired programs downloaded in two channels.