×

Asymptotically optimal dualization algorithms. (English. Russian original) Zbl 1326.90049

Comput. Math. Math. Phys. 55, No. 5, 891-905 (2015); translation from Zh. Vychisl. Mat. Mat. Fiz. 55, No. 5, 895-910 (2015).
Summary: The design of efficient on average algorithms for discrete enumeration problems is studied. The dualization problem, which is a central enumeration problem, is considered. New asymptotically optimal dualization algorithms are constructed. It is shown that they are superior in time costs to earlier constructed asymptotically optimal dualization algorithms and other available dualization algorithms with different design features.

MSC:

90C09 Boolean programming

Software:

UCI-ml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Johnson, M. Yannakakis, and C. Papadimitriou, “On generating all maximal independent sets,” Inf. Proc. Lett. 27(3), 119-123 (1988). · Zbl 0654.68086 · doi:10.1016/0020-0190(88)90065-8
[2] T. Eiter, G. Gottlob, and K. Makino, “New results on monotone dualization and generating hypergraph transversals,” SIAM J. Comput. 32(2), 514-537 (2003). · Zbl 1052.68101 · doi:10.1137/S009753970240639X
[3] M. L. Fredman and L. Khachiyan, “On the complexity of dualization of monotone disjunctive normal forms,” J. Algorithms 21, 618-628 (1996). · Zbl 0864.68038 · doi:10.1006/jagm.1996.0062
[4] L. Khachiyan, E. Bows, K. Elbassioni, and V. Gurvich, “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 (2006). · Zbl 1110.68104 · doi:10.1016/j.dam.2006.04.012
[5] Boros, E.; Elbassioni, K., Generating maximal independent sets for hypergraphs with bounded edge-intersections, 488-498 (2004), Berlin · Zbl 1196.05057 · doi:10.1007/978-3-540-24698-5_52
[6] E. Boros, V. Gurvich, K. Elbassioni, and L. Khachiyan, “An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension,” Parallel Process. Lett. 10(4), 253-266 (2000). · doi:10.1142/S0129626400000251
[7] E. V. Djukova, “Asymptotically optimal algorithm for constricting irredundant tests,” Dokl. Akad. Nauk SSSR 233(4), 527-530 (1977).
[8] E. V. Djukova, “Discrete recognition procedures: The complexity of realization,” Pattern Recogn. Image Anal. 13(1), 8-10 (2003).
[9] E. V. Djukova and R. M. Sotnezov, “On the complexity of discrete generation problems,” Dokl. Math. 82(3), 847-849 (2010). · Zbl 1215.68110 · doi:10.1134/S1064562410060025
[10] E. V. Djukova and Yu. I. Zhuravlev, “Discrete methods of information analysis in recognition and algorithm synthesis,” Pattern Recogn. Image Anal. 7(2), 192-207 (1997).
[11] E. V. Djukova, “The Complexity of the Realization of Certain Recognition Procedures,” USSR Comput. Math. Math. Phys. 27(1), 74-83 (1987). · Zbl 0648.68091 · doi:10.1016/0041-5553(87)90121-2
[12] E. V. Djukova, “On the implementation complexity of discrete (logical) recognition procedures,” Comput. Math. Math. Phys. 44(3), 532-541 (2004).
[13] E. V. Djukova and Yu. I. Zhuravlev, “Discrete analysis of feature descriptions in recognition problems of high dimensionality,” Comput. Math. Math. Phys. 40(8), 1214-1227 (2000). · Zbl 0996.68162
[14] E. V. Djukova and A. S. Inyakin, “Asymptotically optimal construction of irredundant coverings of an integer matrix,” Mat. Voprosy Kibern. 17, 235-246 (2008).
[15] E. V. Djukova and P. M. Sotnezov, “On the complexity of the dualization problem,” Comput. Math. Math. Phys. 52(10), 1472-1481 (2012). · Zbl 1274.68137 · doi:10.1134/S0965542512100090
[16] Djukova, E. V.; Prokofjev, P. A., On asymptotically optimal enumeration for irreducible coverings of a Boolean matrix, 96-105 (2014) · Zbl 07310243
[17] K. Murakami and T. Uno, “Efficient Algorithms for Dualizing Large-Scale Hypergraphs,” Proc, 15. · Zbl 1288.05188
[18] K. Murakami and T. Uno, “Efficient algorithms for dualizing large-scale hypergraphs,” Discrete Appl. Math. 170, 83-94 (2014). · Zbl 1288.05188 · doi:10.1016/j.dam.2014.01.012
[19] UCI machine learning repository; http://archive.ics.uci.edu/ml/.
[20] Frequent itemset mining dataset repository; http://fimi.ua.ac.be/data/. · Zbl 0648.68091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.