Eficientes algoritmos de transmisión para maximizar una función monótona DR-submodular en la retícula entera
Autores: Nguyen, Bich-Ngan T.; Pham, Phuong N. H.; Le, Van-Vang; Snáel, Václav
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Eficientes algoritmos de transmisión para maximizar una función monótona DR-submodular en la retícula entera
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Funciones submodulares
Función DR-submodular
Problemas de optimización
Aprendizaje automático
Algoritmos de transmisión
Restricciones de cardinalidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
En los últimos años, el tema de maximizar funciones submodulares ha atraído mucho interés de las comunidades de investigación. Sin embargo, la mayoría de las funciones submodulares están especificadas en una función de conjunto. Mientras tanto, recientes avances se han estudiado para maximizar una función submodular de retorno decreciente (DR-submodular) en la retícula entera. Debido a que muchas publicaciones muestran que la función DR-submodular tiene amplias aplicaciones en problemas de optimización como problemas de colocación de sensores, asignación óptima de presupuesto, redes sociales y especialmente aprendizaje automático. En esta investigación, proponemos dos algoritmos principales de transmisión para el problema de maximizar una función DR-submodular monótona bajo restricciones de cardinalidad. Nuestros dos algoritmos, que se llaman y , tienen , de ratios de aproximación y , , respectivamente. Realizamos varios experimentos para investigar el rendimiento de nuestros algoritmos basados en el problema de asignación de presupuesto sobre el modelo de influencia bipartita, una instancia del problema de maximización de funciones submodulares monótonas sobre la retícula entera. Los resultados experimentales indican que nuestros algoritmos propuestos no solo proporcionan soluciones con un alto valor de la función objetivo, sino que también superan a los algoritmos de vanguardia en términos tanto del número de consultas como del tiempo de ejecución.
Descripción
En los últimos años, el tema de maximizar funciones submodulares ha atraído mucho interés de las comunidades de investigación. Sin embargo, la mayoría de las funciones submodulares están especificadas en una función de conjunto. Mientras tanto, recientes avances se han estudiado para maximizar una función submodular de retorno decreciente (DR-submodular) en la retícula entera. Debido a que muchas publicaciones muestran que la función DR-submodular tiene amplias aplicaciones en problemas de optimización como problemas de colocación de sensores, asignación óptima de presupuesto, redes sociales y especialmente aprendizaje automático. En esta investigación, proponemos dos algoritmos principales de transmisión para el problema de maximizar una función DR-submodular monótona bajo restricciones de cardinalidad. Nuestros dos algoritmos, que se llaman y , tienen , de ratios de aproximación y , , respectivamente. Realizamos varios experimentos para investigar el rendimiento de nuestros algoritmos basados en el problema de asignación de presupuesto sobre el modelo de influencia bipartita, una instancia del problema de maximización de funciones submodulares monótonas sobre la retícula entera. Los resultados experimentales indican que nuestros algoritmos propuestos no solo proporcionan soluciones con un alto valor de la función objetivo, sino que también superan a los algoritmos de vanguardia en términos tanto del número de consultas como del tiempo de ejecución.