The Program Download Problem: Complexity and Algorithms

摘要

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 polynomi-ally 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.