Asymptotically optimal dualization algorithms¶
Autores: E. V. Djukova; P. A. Prokofjev
Publicación: Computational Mathematics and Mathematical Physics, 55(5), 891–905, 2015
Familia: Escuela rusa (dualización)
Clave BibTeX: djukova2015
Resumen de los autores¶
Pendiente: se copia literal del PDF.
Qué leímos y para qué¶
Leído completo (traducción al inglés). Es la traducción del artículo de 2014 en Mach. Learn. Data Anal.; no son dos conjuntos de experimentos.
Nuestro resumen¶
Fuente primaria de RUNC, RUNC-M y PUNC en inglés (el original es de 2014 en ruso). RUNC-M elige en cada nodo la fila no cubierta de menor peso entre las columnas aún no probadas ni prohibidas, ramifica por sus columnas y filtra las columnas prohibidas en toda la submatriz (filtrado completo, P6). RUNC hace lo mismo con la primera fila no cubierta.
Presenta un esquema general de «algoritmos de segundo tipo» que incluye OPT, MMCS, RS, RUNC y PUNC, y afirma que el enfoque de MMCS y RS «no es nuevo»: la condición crit equivale a la compatibilidad de columnas de Djukova (1977).
Experimentos en C++ con bits contra MMCS y RS de Uno, 20 matrices por tamaño, corte de 600 s. RUNC-M gana en aleatorias densas y en datos reales; MMCS y RS ganan en hipergrafos modelo. No dicen hardware ni opciones de SHD, y describen MMCS con la primera fila, no con la mínima.
Para el proyecto: br-pivot es RUNC-M reconstruido desde fast-BR, así que no se presenta como nuevo. La primera comparación que reclamamos vale solo para los algoritmos de testores.