Actualización para los asesores, 2026-11-19¶
Para Pancho (J. Fco. Martínez-Trinidad), Ariel (J. A. Carrasco-Ochoa) y Lazo (M. S. Lazo-Cortés). Es lo avanzado desde lo que les presenté el martes por la noche (errores en el código publicado, RUNC-M y la nueva tesis del artículo). Base: docs/plan-articulo.md, docs/articulos-por-conseguir.md.
Tesis, sin cambios de fondo¶
Los algoritmos de testores/reductos no se habían comparado con los de minimal hitting sets. Comparamos tres familias en un marco validado por conjunto de reductos: testores (fast-BR, fast-CT_EXT, GCreduct), Murakami-Uno (MMCS, RS) y la escuela rusa (RUNC-M). La fila pivote por nodo, que explica la ventaja de MMCS, no la presentamos como idea nueva: es RUNC-M.
Lo que ya tenemos de la literatura¶
- Djukova y Prokofjev 2015 (el que envió Pancho), leído completo. Confirma que RUNC-M es lo que dijimos y que la idea de
critde MMCS es la compatibilidad de columnas de Djukova (1977). Sus experimentos no dicen hardware ni opciones de SHD, y describen MMCS con la primera fila, no la mínima: hay que medir cuánto de su ventaja es eso. - Alba-Cabrera et al. (PRL 2016 y CIARP 2013), que envió Eduardo. Generadores de matrices con número de testores conocido por fórmula (
φ,θ,γ). Comprobé las fórmulas de su ejemplo con nuestra referencia. Solo midieron BT, LEX y FastCTExt. - RegularSearch (2023) y su versión paralela, enviados por Jairo Lefebre. Compara con FastBR, GCreduct, RoPM y YYC, no con MMCS, RS ni RUNC-M. Su lista
LVes un pivote estático por profundidad. Gana en densas y pierde en ralas, como RUNC-M. - RoPM (2021). Compara solo con fast-BR y GCreduct y parece usar la fila de menos unos como pivote. Hay que decir qué hace distinto y no presentar el pivote como ausente en la línea de testores.
- Leídos además: Alba-Cabrera 2019 (BM ↔ hipergrafo, Teorema 3), González-Guevara 2019, Murakami-Uno (versión final de DAM), BR y fast-BR originales, Djukova-Inyakin 2008, y el resumen de MMCS y RCC-MAS (prueba de que recorren el mismo árbol,
docs/rccmas-vs-mmcs.md). - Efecto: la «primera comparación» de algoritmos latinoamericanos contra MMCS y RS sigue en pie frente a todos estos artículos. No vale para RUNC-M, que ya se comparó con MMCS y RS.
Comunicación con autores¶
Estado según lo que Vladimir me dijo: los correos 1, 2, 3, 5 y 6 salieron. No tengo registradas las fechas de envío, ni que el 4 saliera tal cual (Jairo contestó). Los borradores están en docs/correspondencia/.
Sin respuesta todavía¶
| Autor(es) | Qué pedimos | Qué bloquea |
|---|---|---|
| E. V. Djukova y P. A. Prokofjev (Rusia; correo en ruso) | Su artículo de 2014 en Mach. Learn. Data Anal., el de OPT (Doklady 2007), permiso para usar y citar RUNC-M, y si conocen comparaciones previas | Prioridad de RUNC-M y OPT; permiso de RUNC-M en un repositorio público |
| A. G. Nikiforov (Rusia; correo en ruso) | Licencia del C++ de RUNC-M, que recuperamos de Software Heritage | Poder publicar la comparación con RUNC-M. Pista nueva: el artículo de 2015 apunta a un SourceForge de Prokofjev cuya página declara Creative Commons Attribution; sin verificar que cubra ese código |
| J. Pino Gómez y Y. Villuendas Rey (RoPM) | Código y matrices de RoPM; relación con la fila pivote | Incluir RoPM como baseline y no solapar con br-pivot |
| Zhou, Miao, Feng y Sun (CAMARDF, China; correo en chino con versión en inglés) | Permiso para Camardf.java, escrito leyendo su C++ sin licencia |
Publicar Camardf.java. Sin permiso lo declaramos reimplementado desde el artículo, y habría que comprobar que lo es |
Los correos en ruso y chino los redacté yo, sin revisión de un hablante nativo. Las direcciones de los autores rusos y chinos vienen de artículos de 2009 y 2016 y pueden estar caducas. Con ellos no hay un amigo en común, a diferencia de los latinoamericanos.
Con respuesta¶
- Jairo Lefebre (RegularSearch). Envió RegularSearch, la versión paralela y dos imágenes con resultados de FastRS. Nos dice que FastRS, aún sin publicar, gana a RS y MMCS a densidad alta y no recuerda qué algoritmos en C++ usó. Mi lectura de las imágenes es inferencia y se la confirmo en la respuesta. En la respuesta (borrador, sin enviar) le cuento qué hacemos y los errores de conteo que encontramos en FastBR y GCreduct, y le pido el código, la licencia y detalles de las figuras. No le doy tiempos. También le señalo dos errores en el pseudocódigo del preprint paralelo. Riesgo: si publica FastRS antes, la novedad del artículo se estrecha.
- Eduardo Alba-Cabrera. Envió los dos artículos. No hay inconveniente en que reimplementemos los operadores y los citemos. Sugiere preguntar a Salvador Godoy-Calderon por implementaciones (quizá en MATLAB) y pide que le contemos el uso de las matrices. Respuesta en borrador, sin enviar.
Artículos que aún no tenemos¶
Conseguidos hoy en abierto: Djukova-Prokofjev 2014 en Mach. Learn. Data Anal. (el original de RUNC-M, esencialmente igual al de 2015) y el de Prikl. Diskret. Mat. 2014 (AO2K, AO2M). Además, el repositorio de Prokofjev (ppprok/dual) trae RUNC-M con licencia MIT, lo que desbloquea el permiso del código si lo adoptamos.
| Artículo | Para qué | Cómo conseguirlo |
|---|---|---|
| Djukova-Inyakin, Doklady RAN 413(5), 2007 y el informe del VC RAN 2006 | Primera publicación de OPT | Correo 1; no los encontré en abierto |
| Rango de páginas de Djukova-Inyakin 2008 | Tres obras de Djukova dicen 235–246 y el PDF trae 247–262 impreso | Citar 247–262 con nota |
| Alba-Cabrera et al., CIARP 2012 (LNCS 7441, 813–820) y la versión extendida con BR | Antecedente de los generadores; resultados con algoritmos internos | Eduardo (pregunta 2 del borrador) |
| Versiones publicadas de MinReduct, sRGA y GCreduct (volumen y páginas) | Citas finales | Son nuestras: ¿ustedes las tienen? |
| MiLIT: autores y origen del JAR | Decidir si entra al marco | Sin autor identificado |
| Kavvadias-Stavropoulos 2005, Toda (HTC-BDD), Boros-Makino 2016, Conte-Kanté-Uno, Bläsius et al. | Descartar antecedentes de la fila mínima con filtrado completo | KS es de acceso abierto y lo leo yo; el resto por conseguir |
| FastRS (Jairo) | Posible competidor directo | No publicado |
Los latinoamericanos son amigos de ustedes¶
Entiendo que en cada artículo latinoamericano hay al menos un autor conocido de ustedes. Ahí su intermediación vale más que otro correo mío:
- RoPM (Pino y Villuendas): el correo está sin respuesta. Lo que necesito es el código.
- Jairo y Ruiz-Shulcloper: decidir con ustedes cuánto contamos.
- Alba-Cabrera y Godoy-Calderon: ya respondieron; solo falta la pregunta por implementaciones.
- BR y fast-BR (Lias-Rodríguez, Pons-Porrata, Sanchez-Diaz): no he escrito; tengo los artículos. Solo necesitaría contactarlos si queremos código o la versión extendida.
Lo que sigue (esta semana)¶
- Generadores
φ,θ,γ(Alba-Cabrera): ya implementados (experiments/lib/synth.py) y verificados por conjunto contra la referencia; falta usarlos como verdad de base en matrices grandes. - Medir RUNC-M contra SHD-MMCS para separar fila mínima de filtrado (ver arriba).
- Corridas completas y reductos más cortos (calendario hacia IJCRS, 15 de diciembre).
Preguntas para ustedes¶
- ¿Pueden escribir o llamar a Pino y Villuendas (RoPM) para que respondan? Y de los rusos y chinos: ¿alguno tiene un contacto o conoce una dirección vigente de Djukova, Prokofjev, Nikiforov o de los autores de CAMARDF? El permiso para RUNC-M y el código de RoPM bloquean parte del artículo.
- ¿Qué tanto contamos a Jairo, dado que FastRS no está publicado? Mi propuesta es decir qué hacemos y citarlo como trabajo en preparación; con ustedes decidimos si damos resultados.
- ¿IJCRS o MCPR, y qué máquina usamos para las corridas largas?
- ¿Conocen una comparación publicada de testores contra MMCS o RS que se me haya escapado?