Informatics and Applications
2017, Volume 11, Issue 3, pp 113-122
ON PARALLELIZATION OF ASYMPTOTICALLY OPTIMAL DUALIZATION ALGORITHMS
- E. V. Djukova
- A. G. Nikiforov
- P. A. Prokofyev
Abstract
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.
[+] References (20)
- Johnson, D., and C. Papadimitriou. 1988. On generating all maximal independent sets. Inform. Process. Lett. 27(3):119—123.
- Eiter, T., G. Gottlob, and K. Makino. 2003. New results on monotone dualization and generating hypergraph transversals. SIAMJ. Comput. 32(2):514—537.
- Fredman, M., and L. Khachiyan. 1996. On the complexity of dualization of monotone disjunctive normal forms. J. Algorithm. 21(3):618—628.
- Khachiyan, L., E. Boros, K. Elbassioni, and V. Gurvich. 2006. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. Discrete Appl. Math. 154(16):2350—2372.
- Boros, E., V. Gurvich, K. Elbassioni, and L. Khachiyan. 2000. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Processing Lett. 10(04):253—266.
- Boros, E., K. Elbassioni, V. Gurvich, and L. Khachiyan. 2004. Generating maximal independent sets for hyper-graphs with bounded edge-intersections. Latin American Symposium on Theoretical Informatics. 488—498.
- Djukova, E. 1977. On an asymptotically optimal algorithm for constructing irredundant tests. Sov. Math. Dokl. 18(2):423—426.
- Djukova, E. 1987. The complexity of the realization of certain recognition procedures. Comp. Math. Math. Phys. 27(1):74—83.
- Djukova, E., and Y. Zhuravlev. 1997. Discrete methods of information analysis in recognition and algorithm synthesis. Pattern Recognition Image Anal. 7(2):192—207.
- Djukova, E., and Y. Zhuravlev. 2000. Discrete analysis of feature descriptions in recognition problems of high dimensionality. Comp. Math. Math. Phys. 40(8):1214—1227.
- Djukova, E. 2003. Discrete recognition procedures: The complexity of realization. Pattern Recognition Image Anal. 13(1):8—10.
- Djukova, E. 2004. On the implementation complexity of the realization of discrete (logical) recognitionprocedures. Comp. Math. Math. Phys. 44(3):532—541.
- Djukova, E., and A. Inyakin. 2008. Asimptoticheski optimal’noe postroenie tupikovykh pokrytiy tselochislennoy matritsy [Asymptotically optimal irredundent tests enumeration for integer matrix]. Matematicheskie Voprosy Kibernetiki [Mathematical Problems of Cybernetics] 17:235-246.
- Kudryavtsev, V., and A. Andreev. 2010. Test recognition. J. Math. Sci. 169(4):457-480.
- Djukova, E., and P. Prokofyev. 2014. Ob asimptoticheski optimal’nomperechislenii neprivodimykh pokrytiy bulevoy matritsy [On asymptotically optimal enumeration for irreducible coverings of boolean matrix]. Prikladnaya Diskretnaya Matematika [Discrete Applied Mathematics] 1:96-105.
- Murakami, K., and T. Uno. 2011. Efficient algorithms for dualizing large-scale hypergraphs. CoRR. abs/1102.3813.
- Murakami, K., and T. Uno, 2014. Efficient algorithms for dualizing large-scale hypergraphs. Discrete Appl. Math. 170:83-94.
- Djukova, E., and P. Prokofyev. 2015. Asymptotically optimal dualization algorithms. Comp. Math. Math. Phys. 55(5):891-905.
- Khachiyan, L., E. Boros, V. Gurvich, and K. Elbassioni. 2007. Computing many maximal independent sets for hypergraphs in parallel. Parallel Processing Lett. 17(2):141-152.
- Djukova, E., A. Nikiforov, and P. Prokofyev. 2014. Statisticheski effektivnaya skhema rasparallelivaniya algoritmov dualizatsii [Statistically efficient parallel scheme for dualization algorithms]. Mashinnoe obuchenie i analiz dannykh [J. Machine Learning Data Anal.] 1(7):843-853.
[+] About this article
Title
ON PARALLELIZATION OF ASYMPTOTICALLY OPTIMAL DUALIZATION ALGORITHMS
Journal
Informatics and Applications
2017, Volume 11, Issue 3, pp 113-122
Cover Date
2017-09-30
DOI
10.14357/19922264170313
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
discrete enumeration problem; dualization; asymptotically optimal algorithm; irreducible covering of a Boolean matrix; polynomial-time delay algorithm; parallel dualization algorithm
Authors
E. V. Djukova  ,  , A. G. Nikiforov  , and P. A. Prokofyev
Author Affiliations
Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
M.V. Lomonosov Moscow State University, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
Technische University of Munich, 21 Arcisstrasse, Munich 80333, Germany
|