Resumen: El problema de cobertura de conjunto mínimo (MSCP) es un problema clásico de optimización combinatoria NP-duro con numerosas aplicaciones en ciencia e ingeniería. Aunque se ha propuesto una amplia gama de enfoques exactos, aproximados y metaheurísticos, la mayoría de los métodos tratan implícitamente las instancias de MSCP como monolíticas, pasando por alto posibles propiedades estructurales intrínsecas del universo. En este trabajo, investigamos el concepto de emph{segmentabilidad del universo} en el MSCP y analizamos cómo la descomposición estructural intrínseca (segmentabilidad del universo) puede explotarse para mejorar la optimización heurística. Proponemos una estrategia de preprocesamiento eficiente basada en la unión de conjuntos disjuntos (union–find) para detectar componentes conectados inducidos por la co-ocurrencia de elementos dentro de subconjuntos, permitiendo la descomposición de la instancia original en subproblemas independientes. Cada subproblema se resuelve utilizando la metaheurística GRASP y se combinan soluciones parciales sin comprometer la viabilidad. Amplios experimentos en instancias de referencia estándar y conjuntos de datos sintéticos a gran escala muestran que explotar la segmentación natural del universo mejora consistentemente la calidad y la escalabilidad de la solución, particularmente para instancias grandes y estructuralmente descomponibles. Estas ganancias están respaldadas por una representación de conjunto sucinta a nivel de bits que permite operaciones de conjunto eficientes, lo que hace que el enfoque propuesto sea computacionalmente práctico a escala.
Publicado originalmente en export.arxiv.org el 6 de abril de 2026.
Ver fuente original
