logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro