On parallelization of asymptotically optimal dualization algorithms
E. V. Djukovaab, A. G. Nikiforovc, P. A. Prokofyeva
a Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
b M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1,
Moscow 119991, Russian Federation
c Technische University of Munich, 21 Arcisstrasse, Munich 80333, Germany
The main goal of the paper is to develop and implement an approach to building efficient parallel algorithms for intractable enumeration problems and to apply this approach to one of the central enumeration problems, i. e., dualization. Asymptotically optimal algorithms for dualization are considered to be the fastest among the known ones. They have a theoretical justification of the efficiency on average. The size of enumerated set in the dualization problem grows exponentially with the size of the input; thus, parallel computations are reasonable to be utilized. The authors introduce the static parallelizing scheme for asymptotically optimal algorithms of dualization and present the results of the testing. Statistical processing of the experimental results is conducted in order to determine the kind of distribution of the random variables, representing the size of the subtasks for parallel computation. The conditions, under which the schema demonstrates almost maximum speedup and quite uniform processors load, are discovered.
discrete enumeration problem; dualization; asymptotically optimal algorithm; irreducible covering of a Boolean matrix; polynomial-time delay algorithm; parallel dualization algorithm.
|Russian Foundation for Basic Research
|The research was supported by the Russian Foundation for Basic Research (projects Nos. 16-01-00445-a and 15-51-05059).
PDF file (309 kB)
E. V. Djukova, A. G. Nikiforov, P. A. Prokofyev, “On parallelization of asymptotically optimal dualization algorithms”, Inform. Primen., 11:3 (2017), 113–122
Citation in format AMSBIB
\by E.~V.~Djukova, A.~G.~Nikiforov, P.~A.~Prokofyev
\paper On parallelization of asymptotically optimal dualization algorithms
\jour Inform. Primen.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|