Saltar a contenido

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 crit de 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 LV es 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

  1. ¿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.
  2. ¿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.
  3. ¿IJCRS o MCPR, y qué máquina usamos para las corridas largas?
  4. ¿Conocen una comparación publicada de testores contra MMCS o RS que se me haya escapado?