Saltar a contenido

Revisión bibliográfica: ¿está publicado br-pivot?

Fecha: 2026-11-17. Algoritmo revisado: java/src/mhs/Br.java, modo -mode pivot (en el runner, br-pivot).

Veredicto corto

Sí, en lo esencial ya está publicado. br-pivot coincide en su núcleo con RUNC-M de E. V. Djukova y P. A. Prokofjev (2014–2015). RUNC-M elige en cada nodo la fila no cubierta de menor peso respecto a las columnas candidatas actuales, ramifica solo por sus columnas y, al crear cada hijo, elimina de forma ansiosa de toda la lista candidata las columnas "prohibidas" (la prueba de fila crítica o de soporte). Los propios autores lo describen como una combinación del algoritmo OPT, que filtra toda la lista como BR, con la regla de ramificación de MMCS. Esa es exactamente nuestra descripción de br-pivot. Además, en esa línea se comparó RUNC-M con MMCS y RS (código de Uno) y se reportó que RUNC-M es más rápido en la mayoría de los casos. Confianza alta: leí el texto completo de dos fuentes primarias.

Lo que no encontré publicado es la derivación desde fast-BR (línea latinoamericana de testores típicos) ni una comparación de BR, fast-BR, CT_EXT, LEX, YYC o GCreduct contra MMCS o RS.

1. Preguntas

  1. ¿Está publicada la combinación de filtrado ansioso de la lista candidata (estilo BR, fast-BR o LEX) con la ramificación dinámica por la fila no cubierta mínima en cada nodo?
  2. En la línea de testores y reductos, ¿algún algoritmo elige la fila pivote en cada nodo y no solo en la raíz?
  3. ¿Alguien comparó algoritmos de testores (BR, fast-BR, CT_EXT, YYC, LEX, GCreduct) contra MMCS o RS?
  4. ¿Cuáles son los 3 a 5 trabajos más cercanos y en qué difieren de br-pivot?

2. Método de búsqueda

Bases y herramientas. La API de Semantic Scholar devolvió 429 (límite de tasa) en todos los intentos y no se usó. En su lugar usé OpenAlex, con búsqueda y con el filtro cites:. También usé búsqueda web general, arXiv (PDF completos), Math-Net.ru, el repositorio del FRC CSC (RAS), CyS (IPN), el repositorio ITESO y el material local (legacy/thesis, legacy/latex_inaoe).

Seguimiento de citas (OpenAlex, 2026-11-17). - Trabajos que citan MMCS: 110 a la versión DAM 2014 (W2788537315) y 27 a la versión SDM 2013 (W1630375812). - Trabajos que citan fast-BR (IJPRAI 2013, W2058217402): 21. - Intersección: vacía. OpenAlex no registra ningún trabajo que cite a la vez fast-BR y MMCS.

Consultas usadas (muestra). - "Efficient algorithms for dualizing large-scale hypergraphs" - "typical testors elimination of gaps reduction of columns" - "Djukova Prokofjev RUNC-M asymptotically optimal dualization algorithm row minimal number of ones" - "testor algorithm compared MMCS Murakami Uno typical testors hitting sets" (búsqueda extendida) - "irreducible testor" "minimal transversal" Alba-Cabrera 2019 … - "Symbolic Learning for Improving the Performance of Transversal-Computation Algorithms" BR MMCS - "Построение и исследование новых асимптотически оптимальных алгоритмов дуализации" - all reducts discernibility matrix branch on shortest clause … - Kavvadias Stavropoulos "generalized nodes" …

Textos completos leídos: arXiv 1102.3813 (MMCS), arXiv 1601.02939 (encuesta de Gainer-Dewar y Vera-Licona), arXiv 1605.06692 (Djukova, Nikiforov y Prokofyev), la tesis de Prokofjev (2016), la revisión de Sánchez-Díaz et al. (2022), Guevara et al. (2023, LEX), arXiv 2608.02159 (Hörmann y Schirneck) y la tesis de Rodríguez-Diez (2022, local).

3. Hallazgos por pregunta

Pregunta 1: la combinación está publicada (RUNC-M)

Hecho: la tesis de Prokofjev describe RUNC-M así.

Fuente: П. А. Прокофьев, Корректное распознавание по прецедентам: построение логических корректоров общего вида и вычислительные аспекты. Tesis de candidato en ciencias, Centro de Cómputo Dorodnitsyn, FRC CSC RAS, Moscú, 2016. Directora: E. V. Djukova. PDF: https://web.frccsc.ru/sites/default/files/docs/ds/002-073-05/diss/02-prokofiev/dis002_prokofiev.pdf. La sección 3.3.5, p. 76, dice:

«В построенных алгоритмах RUNC (аббревиатура от Remove Unallowable Columns) и RUNC-M (RUNC Minimum weight row) комбинируются идеи алгоритмов ОПТ и MMCS.»

Traducción: «en los algoritmos RUNC y RUNC-M se combinan las ideas de los algoritmos OPT y MMCS».

El paso 3 de la iteración (p. 77) dice:

«…в подматрице L(R[H], D[H]) выбирается строка i, не покрытая столбцом j (… алгоритм RUNC-M ищет строку i с наименьшим весом w_i(D[H])), формируется набор C[H′] покрывающих строку i столбцов подматрицы L(R[H], D[H]), и строится подматрица L(R[H′], D[H′]) путем удаления из подматрицы L(R[H], D[H]) покрытых столбцом j строк и, аналогично алгоритму ОПТ, запрещённых для H′ столбцов.»

Traducción: se elige la fila no cubierta de menor peso respecto a las columnas actuales D[H]. Los hijos son las columnas que cubren esa fila. El nuevo subproblema se forma quitando las filas cubiertas y, como en OPT, las columnas prohibidas para H′.

En el Algoritmo 3 (pp. 78–79), BuildSubtreeRUNC elige «RUNC-M: i — строка с минимальным весом w_i(D)» en cada llamada recursiva. CreateNodeRUNC(j) recorre todas las columnas p ∈ D y borra las que cubren todas las filas de soporte de algún l ∈ H:

«для всех (p ∈ D) если (a_ip = 1, ∀i ∈ S_l) то удалить p из D; // удалить запрещённые столбцы»

La definición de columna prohibida (p. 71) es la prueba de criticidad de MMCS:

«Столбец j матрицы L называется запрещённым для набора столбцов H, если существует столбец l ∈ H такой, что столбец j покрывает все опорные для (H, l) строки.»

Traducción: una columna es prohibida si cubre todas las filas de soporte (filas críticas) de alguna columna de H.

Sobre el efecto de la regla de fila mínima (p. 77):

«Алгоритм RUNC-M можно назвать «жадным» алгоритмом, минимизирующим число внутренних вершин дерева решений. Алгоритм RUNC работает быстрее RUNC-M в тех случаях, когда матрица является разреженной и в каждой строке примерно одинаковое число единиц.»

Es decir, RUNC-M es un algoritmo «voraz» que minimiza los nodos internos, y RUNC, que toma la primera fila no cubierta, gana en matrices ralas con filas de peso parecido.

Hecho: la versión en inglés con pseudocódigo está en arXiv.

Fuente: E. V. Djukova, A. G. Nikiforov, P. A. Prokofyev, Parallelizing asymptotically optimal algorithms for large-scale dualization problems, arXiv:1605.06692v3, 2016. https://arxiv.org/abs/1605.06692. La sección 3 dice:

"1: C0min = {j ∈ C0 | aij = 1}, where i ∈ R0 is the index of the row with the least sum Σ_{j∈C0} aij; … 7: Eliminate from R the rows that are covered by column j … 11: Eliminate from C the columns that are incompatible with H; 12: call RUNCM(L, H, R, C)"

"A column u is compatible with H if and only if there is no column j ∈ H such that column u covers all rows from S(H, j)."

Sobre MMCS y RS, el mismo artículo dice:

"These algorithms are based on constructing sets of vertices of a hypergraph H satisfying the 'crit' condition, which is equivalent to compatibility condition 2) for the corresponding set of columns of the incidence matrix of H."

Publicaciones originales de RUNC y RUNC-M, según la tesis y el artículo de arXiv. No pude leer el texto completo de ninguna de las dos. Math-Net.ru no terminó la descarga en dos intentos y la versión de Springer es de pago. - E. V. Djukova, P. A. Prokofjev, «Построение и исследование новых асимптотически оптимальных алгоритмов дуализации», Машинное обучение и анализ данных, 1(8), 2014, pp. 1048–1067. - E. V. Djukova, P. A. Prokofjev, "Asymptotically optimal dualization algorithms", Computational Mathematics and Mathematical Physics 55(5), 2015, pp. 891–905. DOI: 10.1134/S0965542515050103. Original en ruso: Zh. Vychisl. Mat. Mat. Fiz. 55(5), 895–910, DOI: 10.7868/S0044466915050105. https://www.mathnet.ru/eng/zvmmf10212

Hecho: el filtrado ansioso con la fila mínima en cada nodo no está en MMCS, que lo descarta a propósito.

Fuente: K. Murakami, T. Uno, "Efficient algorithms for dualizing large-scale hypergraphs", Discrete Applied Mathematics 170 (2014) 83–94, DOI: 10.1016/j.dam.2014.01.012. Leí la versión final de DAM (2014) y la de arXiv 1102.3813v2 (2011), https://arxiv.org/abs/1102.3813. El texto citado es idéntico; en DAM es la sección 3.6 (en arXiv, 4.6):

"The pruning method described above can be applied to any vertex. However, applying it to all possible vertices may take a long time compared with other parts of an iteration. … Thus, to make the computation time stable, we prune only the vertices in CAND ∩ F, which are the vertices to be added to the current solution."

La sección 3.5 de DAM (4.5 en arXiv) da la regla de ramificación:

"We choose a hyperedge including the smallest number of vertices which have not been pruned, so that the number of recursive calls generated will be small."

Hecho: Hörmann y Schirneck formalizan MMCS con la poda limitada a los candidatos de ramificación.

Fuente: B. Hörmann, M. Schirneck, "Minimal-to-Maximal Conversion Search Is Not Output-Polynomial", arXiv:2608.02159, 2026. https://arxiv.org/abs/2608.02159. Definen la heurística mínima ("Min-heuristic: … minimizing the cardinality |E ∩ C| over all unhit edges") y la poda de violadores solo sobre los candidatos de ramificación v ∈ E ∩ C. Proponen además unhit degree sorting para ordenar esos candidatos. No mencionan RUNC-M, a Djukova ni los testores.

Hecho: la encuesta de Gainer-Dewar y Vera-Licona no incluye a Djukova, RUNC ni testores.

Fuente: A. Gainer-Dewar, P. Vera-Licona, "The minimal hitting set generation problem: algorithms and computation", SIAM J. Discrete Math. 31(1), 2017, DOI: 10.1137/15M1055024; arXiv:1601.02939. Su tabla 1 lista HST, BMR, DL, KS, FK-A, FK-B, BOOL, STACCATO, ParTran, Knuth, HTC-BDD, MHS2, MTMiner, MMCS, RS, pKBEG, pELB, pBM, PrimDecomp e IntProg. Una búsqueda en el texto de "testor", "Djukova" y "RUNC" no da resultados. Ninguno de esos algoritmos, tal como los describe la encuesta, combina el filtrado ansioso con la fila mínima en cada nodo. Esto se basa en las descripciones de la encuesta, no en la lectura de cada artículo original.

No revisado a texto completo: Eiter, Gottlob y Makino; Toda (HTC-BDD); Boros y Makino 2016; Conte, Kanté y Uno; Bläsius et al. (2019, 2022); EC-MHS (2026); la herramienta ASP (2026). Ninguno apareció en las búsquedas como variante de MMCS con filtrado ansioso, y algunos, como HTC-BDD, son de otra familia. Que no haya aparecido no prueba que no exista.

Pregunta 2: línea de testores y reductos

Hechos: - CT_EXT, BR, fast-BR y LEX solo reordenan en la raíz. La revisión de Sánchez-Díaz et al. (2022) dice: "At the beginning, a convenient rearrangement of BM that consists in placing the row with the least number of 1s at the top of BM is carried out. Furthermore, all the columns containing 1 on the first row are translated to the leftmost columns in BM." Fuente: G. Sánchez-Díaz, M. S. Lazo-Cortés, C. A. Aguirre-Salado, I. Piza-Dávila, J. P. García-Contreras, "A review of algorithms to computing irreducible testors applied to feature selection", Artificial Intelligence Review 56, 2023 (en línea 2022). DOI: 10.1007/s10462-022-10162-z. PDF: https://rei.iteso.mx/bitstreams/51e94b6a-c788-4ef7-897a-c067005cefc5/download - La tesis de Rodríguez-Diez (BUAP, 2022), p. 27, describe CT_EXT con la misma regla de raíz: "first, one of the rows of the basic matrix with the fewest number of 1's is selected. Then, the selected row is moved to the top, and all columns in which it has 1, are moved to the left." En sus trabajos futuros (p. ~108) propone un meta-algoritmo que cambie de estrategia durante la búsqueda: "switching the search strategy through the searching process as a function of the basic-matrix's properties". La tesis no menciona MMCS, Murakami ni hitting sets (búsqueda en el texto). Fuente: V. Rodríguez Diez, Development of fast algorithms for reduct computation, tesis doctoral, BUAP, 2022 (copia local en legacy/thesis/). - LEX* también reordena solo en el paso 1: "1: Sort B: Find the row with minimum amount of 1's … Put it as first row in B. Sort columns of B putting as first the ones that have a 1 in the first row." Fuente: I. Guevara, S. Godoy-Calderón, E. Alba, "Adding Learning Capabilities to the LEX Algorithm for Computing Minimal Transversals", Computación y Sistemas 27(2), 2023, DOI: 10.13053/CyS-27-2-4243. https://cys.cic.ipn.mx/index.php/CyS/article/view/4243 - YYC y CT ordenan las filas una sola vez. La revisión de 2022 dice: "For YYC algorithm, BM rows are sorted in ascending order of the number of ones in each row" y "In CT algorithm, a row with the least amount of 1s is selected as the first row of BM". - Rusia (escuela de Zhuravlev): RUNC-M sí elige la fila en cada nodo (ver pregunta 1). Inferencia: el problema que resuelven, las coberturas irreducibles de una matriz booleana o tests sin salida («тупиковые тесты»), es el mismo que los testores típicos sobre la matriz básica. Que el término latinoamericano venga de esa escuela es conocimiento del área que no verifiqué en esta búsqueda. Así, la regla dinámica sí existe en una línea de testores, aunque no en la latinoamericana. - Rough sets: no encontré algoritmos de reductos exactos con ramificación dinámica por la cláusula de discernibilidad más corta. La búsqueda fue superficial y es la pregunta con menor cobertura.

No revisado a texto completo: RoPM (Pino Gómez et al., IEEE Access 2021, DOI 10.1109/ACCESS.2021.3112385; solo el resumen), GCreduct (Information Sciences 2018, DOI 10.1016/j.ins.2017.12.027), MinReduct, CAMARDF, sRGA, MiLIT y el artículo original de fast-BR (IJPRAI 27(8), 2013, DOI 10.1142/S0218001413500225). Para estos me apoyo en la revisión de 2022, la tesis local y el código en java/fixed/. El IEEE no me dejó descargar los PDF de acceso abierto con el método automático (el sistema bloqueó el intento con cookies) y no lo forcé.

Pregunta 3: comparaciones de testores contra MMCS o RS

Hechos: - Línea rusa: sí. La tesis de Prokofjev (2016), sección 3.4, compara OPT, RUNC, RUNC-M, PUNC, AO1/AO1K/AO1M y AO2/AO2K/AO2M contra MMCS y RS. Las tablas 3.1–3.23 cubren matrices aleatorias, hipergrafos modelo y datos aplicados (WIN, LOSE, ACC, BMS). La tesis dice que el código de MMCS y RS se tomó de Uno: «Исходные коды программ алгоритмов MMCS и RS взяты из http://research.nii.ac.jp/~uno/dualization.html». - Conclusión de la tesis (p. 58): sus algoritmos «в большинстве случаев опережают алгоритмы из [76, 77]», es decir, superan a MMCS y RS en la mayoría de los casos. - Ejemplo de la tabla 3.21 (LOSE, m = 16635): MMCS 519,5 s, RUNC-M 137,7 s, RS > 600 s. - Contraejemplo de la tabla 3.23 (BMS, m = 30405): RUNC-M 315,6 s, MMCS > 600 s, RS > 600 s. - La propia tesis reconoce que RS y MMCS ganan en los hipergrafos umbral TH(n) y SDTH(n), que son muy ralos: «Дуализацию порогового графа TH(n) и самодвойственного гиперграфа SDTH(n) быстрее других выполняют алгоритмы RS и MMCS». - arXiv:1605.06692 llama a RUNC-M "the fastest known dualization algorithm". - Línea latinoamericana (BR, fast-BR, CT_EXT, LEX, YYC, GCreduct): no encontré ninguna comparación con MMCS ni RS. Indicios: - La intersección de citas en OpenAlex está vacía. - La revisión de 2022 no cita a Murakami ni a Uno; solo menciona la relación con transversales mínimas por Alba-Cabrera et al. (2019). - Guevara et al. (2023) no mencionan MMCS en el texto. - Según Guevara et al. (2023), la técnica de aprendizaje simbólico de González-Guevara et al. (IEEE Access 7, 2019, 19752–19761, DOI 10.1109/ACCESS.2019.2895296) "has been tested only on two algorithms, BR [15] and YYC". Ese artículo de 2019 cita MMCS según OpenAlex. No leí su texto completo. - Alba-Cabrera et al., "On the Relation Between the Concepts of Irreducible Testor and Minimal Transversal", IEEE Access 7 (2019) 82809–82816, DOI 10.1109/ACCESS.2019.2922231, habla en su resumen de "the equivalence of the result of two specific algorithms, one from each field". No pude leer el texto completo y no sé cuáles son esos dos algoritmos ni si hay experimentos.

Pregunta 4: trabajos más cercanos y diferencias con br-pivot

# Trabajo Qué comparte con br-pivot Qué difiere
1 RUNC-M (Djukova y Prokofjev 2014, 2015; tesis de Prokofjev 2016; arXiv:1605.06692) En cada nodo elige la fila no cubierta de peso mínimo respecto a las columnas candidatas actuales. Ramifica solo por sus columnas y excluye las ya probadas (удалить j из D). Al crear el hijo quita las filas cubiertas y todas las columnas prohibidas de la lista, con la misma prueba de criticidad. (a) br-pivot también quita las columnas sin contribución; RUNC-M no lo hace de forma explícita, aunque esas columnas no pesan en w_i(D) y nunca generan hijos. Inferencia: el árbol es el mismo. (b) br-pivot reporta S+X+y durante el filtrado, un nivel antes, y no abre hijos con menos de 2 columnas. (c) br-pivot fusiona columnas iguales. (d) RUNC-M vacía S_l cuando una fila de soporte de l ya no la cubre ninguna columna de D, lo que abarata pruebas posteriores; no lo veo en el encabezado de Br.java. (e) El orden de los candidatos y el desempate entre filas no se especifican en RUNC-M; br-pivot conserva el orden de fast-BR. Son diferencias de implementación, no de esquema.
2 MMCS (Murakami y Uno 2014) Fila (hiperarista) no cubierta mínima en cada nodo y la misma prueba de criticidad. La poda de violadores es perezosa y se limita a CAND ∩ F (§3.6 de DAM, citada arriba). Las columnas que no cubren nada nuevo no se filtran. El peso de la fila cuenta los vértices "no podados", no una lista ya filtrada por completo.
3 OPT (Djukova e Inyakin 2008, Matematicheskie Voprosy Kibernetiki 17, 247–262, que describe OPT y lo extiende a matrices enteras; la primera publicación de OPT es Djukova e Inyakin, Doklady RAN 413(5), 2007, 596–598; descrito en la tesis de Prokofjev, sección 3.3.2) En cada nodo quita las columnas prohibidas y las nulas, las que no aportan, de toda la submatriz. Es el filtrado ansioso de BR en otra notación. También quita las filas que absorben a otras. No usa fila pivote: «в подматрицу L(R[H], C[H]) включаются только совместимые с H и ненулевые столбцы … каждый столбец … порождает дочернюю … вершину». Ramifica por todas las columnas compatibles, como fast-BR fuera de la raíz. Leí el artículo de 2008 (papers/mvk2008_247.pdf, §2 y §3) y lo confirma: ramifica por conjuntos de columnas en orden de índice, quita filas que absorben y columnas nulas, sin fila pivote. No leí la publicación primaria (Doklady 2007).
4 fast-BR / BR / LEX / CT_EXT (Lias-Rodríguez y Sanchez-Diaz 2013; Lias-Rodríguez y Pons-Porrata 2009; Santiesteban y Pons 2003; Sanchez-Diaz y Lazo-Cortés 2007) Lista ordenada, pruebas de contribución y exclusión, poda por huecos (gaps) y fusión de columnas repetidas (fast-BR). La fila más rala se elige solo en la raíz (revisión de 2022, tesis de 2022 y LEX* de 2023, citados arriba).
5 RUNC (mismas fuentes que RUNC-M) y RS (Murakami y Uno 2014) RUNC hace el mismo filtrado ansioso que RUNC-M. Ambos toman la primera fila no cubierta en orden fijo, no la mínima. RS además restringe la compatibilidad a las filas anteriores (i-compatibilidad).

Mención aparte: Kavvadias y Stavropoulos, "An Efficient Algorithm for the Transversal Hypergraph Generation", J. Graph Algorithms Appl. 9(2), 2005, 239–264, DOI 10.7155/jgaa.00107. Según fuentes secundarias (no leí el original), agrupan los vértices que aparecen en las mismas hiperaristas ("generalized nodes"). Sería un antecedente de la fusión de columnas iguales, pero procesan las aristas en orden fijo.

4. Veredicto

Hecho. El esquema de br-pivot está publicado como RUNC-M desde 2014–2015, con pseudocódigo en inglés en arXiv desde 2016. Consiste en elegir en cada nodo la fila no cubierta de menor peso sobre los candidatos vigentes, ramificar solo por sus columnas y filtrar de forma ansiosa toda la lista de candidatos con la prueba de criticidad. Los autores lo presentan explícitamente como OPT (filtrado ansioso) + MMCS (regla de fila mínima). También publicaron una comparación con MMCS y RS usando el código de Uno.

Inferencia. br-pivot no es un algoritmo nuevo. Es una reconstrucción independiente de RUNC-M partiendo de fast-BR. Las diferencias encontradas (contribución explícita, reporte adelantado, umbral de 2 columnas, fusión de columnas, orden heredado) son de implementación y no cambian la idea.

Confianza. Alta (~90 %) en que el núcleo coincide con RUNC-M: leí el pseudocódigo y las definiciones en dos fuentes primarias de los mismos autores. Media en que no haya otro antecedente anterior; OPT e incluso Djukova (1977) podrían contener partes. Media-baja en que la línea latinoamericana nunca se haya comparado con MMCS: no tuve acceso a varios textos completos de IEEE Access ni a RegularSearch.

Consecuencia para el artículo (inferencia). No conviene presentar br-pivot como contribución algorítmica. Sí se puede presentar como: - el puente explícito entre fast-BR y RUNC-M/MMCS, citando a Djukova y Prokofjev; - una ablación que aísla el efecto de la fila pivote dinámica dentro de fast-BR; - la primera comparación, hasta donde encontré, de algoritmos de testores latinoamericanos contra MMCS y RS.

Hay que citar RUNC-M y contrastar nuestros tiempos con los suyos. Ellos reportan que RUNC-M supera a MMCS en la mayoría de los casos; nosotros medimos br-pivot hasta 2,6× más lento que MMCS. La discrepancia puede deberse a la implementación (Java contra C++), a las matrices o a la versión de SHD, y merece explicarse.

5. Limitaciones

  • No encontrado no prueba que no exista. La búsqueda cubrió inglés, español y ruso, pero no fue exhaustiva.
  • Semantic Scholar no estuvo disponible (429). El seguimiento de citas usó solo OpenAlex, cuya cobertura de revistas latinoamericanas y rusas es incompleta.
  • Actualización 2026-11-19: Djukova y Prokofjev (2015) ya está leído completo (docs/articulos-por-conseguir.md, cuarta pasada) y confirma la descripción de RUNC-M de esta sección. Sigue sin leerse la versión de 2014 en Машинное обучение и анализ данных. Antes: no leí el texto completo de Djukova y Prokofjev (2015) ni de la versión de 2014 en Машинное обучение и анализ данных. Me apoyo en la tesis de Prokofjev (2016) y en arXiv:1605.06692, de los mismos autores.
  • La versión final de MMCS en DAM 2014 se leyó el 2026-11-18 y coincide con arXiv v2 en la poda restringida; solo cambia la numeración (§3.6 y §3.5).
  • Sin texto completo: KS (2005) y los trabajos de Toda, Boros-Makino, Conte-Kanté-Uno y Bläsius et al. RegularSearch (2023) y su versión paralela se leyeron completos el 2026-11-19 (docs/regularsearch-y-jairo.md). Leídos parcialmente el 2026-11-18 (ver docs/articulos-por-conseguir.md): Alba-Cabrera et al. (2019), González-Guevara et al. (2019), RoPM (2021), BR (2009), fast-BR (2013), GCreduct (2018, preprint), OPT (2008) y las láminas de Djukova.
  • El repositorio con la implementación de RUNC-M citado en arXiv:1605.06692 (github.com/ankifor/dualization-OPT) devuelve 404. Se recuperó de Software Heritage (ver sección 6).

6. Código de RUNC-M recuperado y primera medición (2026-11-17)

Origen. El repositorio de A. Nikiforov ya no existe en GitHub. Software Heritage lo archivó; la última visita completa es de 2024-04-05. La rama RUNCM (revisión bf3fc9c4, 2015-11-03) tiene la versión secuencial en C++ (OPT/), una versión MPI y utilidades. El README atribuye el código a Djukova y Prokofjev (2015). No trae licencia: se puede correr, no redistribuir.

Compilación. scripts/fetch_runcm.sh baja los archivos y compila en third_party/runcm/, que git ignora. El código usa intrínsecos de MSVC (__popcnt, _tzcnt_u32). Un encabezado aparte, compat.h, los define con los builtins de GCC, y tzcnt32(0) devuelve 32 como _tzcnt_u32. Las fuentes no se tocan. En el runner el algoritmo se llama runcm; RUNCM_BIN permite usar otro binario.

Validación. Probé por conjunto contra la referencia de Python 453 matrices: las 442 generadas por verify_fixed.py (aleatorias, columnas repetidas, columnas nulas, columnas llenas y casos borde) y las 11 de tests/. Coincidieron las 453. En las 12 matrices de la ablación, el conteo coincide con MMCS, SHD y br-pivot.

Tiempos. Las 12 matrices de la ablación, una corrida por programa, en la máquina de 2 núcleos. Cuidado al comparar: RUNC-M y SHD miden el tiempo de pared del proceso, con lectura del archivo incluida, y MMCS y br-pivot (Java) miden solo la búsqueda, sin arranque de la JVM. Esto favorece a los programas en Java. Los nodos se cuentan distinto en cada programa.

Matriz Dens. Reductos RUNC-M ms br-pivot ms MMCS (Java) ms SHD-MMCS ms
dermatology 0,34 112.708 59 153 105 109
lung-cancer 0,46 4.183.355 768 987 1.328 2.540
student-mat 0,44 617.921 2.511 2.802 1.928 1.945
sint_4-6 0,17 130.147 1.982 1.709 707 901
sint_6-14 0,32 2.018.970 9.832 12.531 5.993 7.318
sint_11-27 0,52 1.385.756 3.102 3.717 2.019 3.743
sint_23-25 0,80 30.792 29 96 65 72

Las otras cinco matrices (MED, soybean, biodeg, anneal, heart-c) tardan 30 ms o menos con todos los programas y no dicen nada.

Lectura (inferencia). El resultado coincide en parte con lo que reporta Prokofjev: - RUNC-M gana en las matrices más densas (dermatology, lung-cancer y sint_23-25). - MMCS gana en las sintéticas ralas o de densidad media. En sint_4-6 (densidad 0,17), RUNC-M tarda 2,8 veces más que el MMCS en Java y 2,2 veces más que SHD. - La propia tesis dice que MMCS y RS ganan en hipergrafos muy ralos. - br-pivot va cerca de RUNC-M, entre 0,9 y 3,3 veces su tiempo, a pesar de estar en Java.

Por lo tanto, la discrepancia con la tesis no parece venir de nuestra implementación: depende de la densidad. Faltan corridas repetidas, más matrices y medir todo con el mismo reloj antes de concluir.

Medición repetida (experiments/baseline/runcm_vs_mmcs.py, results/runcm_vs_mmcs.{csv,md}). Usé 20 matrices: las 12 sintéticas de 2000x30 (una por banda de densidad) y 8 de UCI. Corrí cada programa 3 veces, alternando los programas, y reporto la mediana. Todos se midieron con el mismo reloj, el tiempo de pared del proceso, al que le resté el arranque medido aparte. El arranque es de 0 a 1 ms para RUNC-M y SHD, y de 86 a 126 ms para la JVM. Para los programas en Java también se guardó el tiempo de búsqueda sola. Los conteos coinciden en las 20 matrices.

Tiempo de RUNC-M dividido por el de MMCS en Java (búsqueda sola). Un valor menor que 1 significa que gana RUNC-M.

Densidad (sintéticas 2000x30) 0,17 0,22 0,27 0,32 0,37 0,42 0,47 0,52 0,57 0,62 0,70 0,80
RUNC-M / MMCS 2,60 2,49 2,17 1,67 1,62 1,70 1,68 1,57 1,33 1,22 0,66 0,12
UCI Filas x columnas Dens. RUNC-M ms SHD-MMCS ms SHD-RS ms MMCS búsqueda ms br-pivot búsqueda ms
dermatology 1103x34 0,34 58 108 84 115 131
lung-cancer 237x56 0,46 767 2.373 4.645 1.384 1.060
student-mat 6253x32 0,44 2.621 1.976 1.319 1.953 2.779

Las otras cinco UCI tardan menos de 10 ms con todos los programas y no sirven para comparar. La dispersión entre corridas suele ser menor al 20 %, pero en las matrices de menos de 300 ms llega al 50 % o más en Java (JIT).

Lectura. - Hecho: en las sintéticas, RUNC-M pierde contra MMCS hasta densidad 0,62 y gana desde 0,70. La desventaja baja de forma monótona con la densidad, de 2,6 veces a 1,2. Contra SHD-MMCS el cruce llega antes: RUNC-M gana desde 0,47. - Hecho: en UCI, RUNC-M gana en dermatology (0,34) y lung-cancer (0,46) y pierde en student-mat (0,44), donde gana SHD-RS. La densidad sola no decide. - Inferencia, por verificar: el filtrado de toda la lista en RUNC-M cuesta más cuantas más filas tiene la matriz. student-mat (6253 filas) y las sintéticas (2000) son las que más filas tienen, y lung-cancer (237) la que menos. dermatology (1103) no encaja del todo. Otras explicaciones posibles: el número de columnas (lung-cancer tiene 56) y la cantidad de reductos por nodo. Para separarlas haría falta un barrido controlado de filas, columnas y densidad. - Inferencia: esto concilia nuestro resultado con la tesis de Prokofjev. RUNC-M es más rápido en matrices densas y en matrices con pocas filas. Para elegir algoritmo, MMCS o RS no dominan en todos los casos.

Barrido controlado (experiments/baseline/runcm_sweep.py, results/runcm_sweep.{csv,md}). Se cambia un factor a la vez alrededor de una matriz base de 1000 filas, 30 columnas y densidad 0,40. Las matrices son aleatorias y básicas por construcción. Cada punto usa 2 semillas y la mediana de 3 corridas. Para RUNC-M y SHD el tiempo es el de pared menos el arranque; para MMCS en Java, la búsqueda sola. Los conteos coinciden en los 34 puntos. Cada valor es la media de las dos semillas.

Factor Valores RUNC-M / MMCS (Java) RUNC-M / SHD-MMCS
Densidad 0,2 · 0,3 · 0,4 · 0,5 · 0,6 · 0,7 1,84 · 1,90 · 1,47 · 1,24 · 0,86 · 0,49 1,27 · 0,95 · 0,75 · 0,58 · 0,52 · 0,39
Filas 125 · 250 · 500 · 1000 · 2000 · 4000 0,77 · 1,07 · 1,27 · 1,50 · 1,56 · 1,61 0,37 · 0,45 · 0,58 · 0,74 · 1,00 · 1,45
Columnas 20 · 24 · 28 · 32 · 36 0,45 · 1,25 · 1,46 · 1,50 · 1,36 0,84 · 0,82 · 0,75 · 0,71 · 0,68

Hechos: - La densidad es el factor más fuerte. Frente a MMCS, la relación baja de 1,9 a 0,5 y el cruce cae entre 0,5 y 0,6. Frente a SHD, el cruce cae entre 0,2 y 0,3. - Las filas también influyen. Con pocas filas gana RUNC-M: con 125 filas tarda 0,77 veces lo que MMCS y 0,37 veces lo que SHD. Con más de 1000 filas la relación frente a MMCS se estabiliza en torno a 1,6, y frente a SHD sigue subiendo. - Las columnas casi no cambian la relación. Con 20 columnas todo tarda menos de 150 ms y la medición es ruidosa.

Inferencias: - Esto explica lung-cancer (237 filas, densidad 0,46): RUNC-M gana. También explica student-mat (6253 filas): RUNC-M pierde. - dermatology no encaja: tiene 1103 filas y densidad 0,34, y aun así RUNC-M gana por 2 veces. Debe intervenir la estructura de los datos reales, por ejemplo columnas correlacionadas o filas muy desiguales. No está explicado. - El MMCS en Java es más rápido que SHD en la mayoría de estos puntos. Por eso el cruce frente a SHD llega antes. Comparar solo contra SHD habría favorecido a RUNC-M.

Consecuencia para el artículo. RUNC-M debe entrar como baseline externo, igual que SHD. Su código no se puede redistribuir sin permiso; la lista de artículos y preguntas está en docs/articulos-por-conseguir.md. - Las citas en ruso están transcritas del PDF de la tesis; las traducciones son mías.