Complexity analysis and algorithms for the Program Download Problem

Chao Peng (), Jie Zhou (), Binhai Zhu and Hong Zhu
Additional contact information
Chao Peng: East China Normal University
Jie Zhou: Shanghai Normal University
Binhai Zhu: Montana State University
Hong Zhu: East China Normal University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 1, No 13, 216-227

Abstract: Abstract 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$$ d and each program appears in each of the $$n$$ n channels at most once, denoted as $$\textit{PDP}(n,1,d)$$ PDP ( n , 1 , d ) , we prove that $$\textit{PDP}(n,1,d)$$ 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)$$ 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)$$ PDP ( 2 , 1 , d ) and $$\textit{PDP}(2,2,d)$$ 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$$ d , we prove that it is fixed-parameter tractable. Finally, we devise an approximation algorithm for $$\textit{MPDP}(2,p,d),\,p\ge 3$$ MPDP ( 2 , p , d ) , p ≥ 3 , which aims to maximize the number of desired programs downloaded in two channels.

Keywords: Program Download Problem; NP-complete; FPT algorithm; Approximation algorithm (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9702-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:1:d:10.1007_s10878-013-9702-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9702-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().