On the parallelization of dynamic programming method for knapsack problem

Mikhail Posypkin, Si Thu Thant Sin

Abstract


The work is dedicated to the practical and theoretical study of parallel variants of the dynamic programming method for the subset sum problem. The standard table based variant of the method is considered as well as its modifications. We perform theoretical and experimental comparison of the effectiveness of the proposed algorithms. For experimental comparison we use an Intel Xeon Phi with 61 computational kernel.

Full Text:

PDF (Russian)

References


Lazarev Alexander A, Werner Frank. A graphical realization of the

dynamic programming method for solving np-hard combinatorial

problems // Computers & Mathematics with Applications. — 2009. —

Vol. 58, no. 4. — P. 619–631.

Kolpakov Roman Maksimovich, Posypkin Mikhail Anatol’evich. Upper

and lower bounds for the complexity of the branch and bound

method for the knapsack problem // Discrete Mathematics and Applications. — 2010. — Vol. 20, no. 1. — P. 95–112.

Kolpakov RM, Posypkin MA, Sin Si Tu Tant. Complexity of solving

the subset sum problem with the branch-and-bound method with domination and cardinality filtering // Automation and Remote Control. —

— Vol. 78, no. 3. — P. 463–474.

Kellerer Hans, Pferschy Ulrich, Pisinger David. Knapsack problems.

Martello Silvano, Toth Paolo. Knapsack problems: algorithms and

computer implementations. — John Wiley & Sons, Inc., 1990.

Gary Michael R, Johnson David S. Computers and intractability: A

guide to the theory of np-completeness. — 1979.

El Baz Didier, Elkihel Moussa. Load balancing methods and parallel

dynamic programming algorithm using dominance technique applied

to the 0–1 knapsack problem // Journal of Parallel and Distributed

Computing. — 2005. — Vol. 65, no. 1. — P. 74–84.

Tan Guangming, Sun Ninghui, Gao Guang R. A parallel dynamic

programming algorithm on a multi-core architecture // Proceedings

of the nineteenth annual ACM symposium on Parallel algorithms and

architectures / ACM. — 2007. — P. 135–144.

Kolpakov Roman Maksimovich, Posypkin Mikhail Anatolevich, Sigal

I Kh. On a lower bound on the computational complexity of a

parallel implementation of the branch-and-bound method // Automation

and Remote Control. — 2010. — Vol. 71, no. 10. — P. 2152–

Kolpakov Roman, Posypkin Mikhail. The lower bound on complexity

of parallel branch-and-bound algorithm for subset sum problem // AIP

Conference Proceedings / AIP Publishing. — Vol. 1776. — 2016. —

P. 050008.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162