Maximización de funciones supermodulares

Question

Tengo una función objetivo real supermodular que quiero maximizar con restricción. La restricción es sobre el tamaño, como |A|=k .

Me pregunto si alguien puede darme más información sobre una solución práctica aplicable a un conjunto grande, en particular lo que podemos decir sobre el algoritmo codicioso.

Gracias de antemano,

Answer 1

Maximizar una función supermodular es como minimizar una función submodular. Se trata de una actividad de tiempo polinómico, para la que se conocen varios algoritmos (buscar en google Algoritmo de norma mínima y encontrará muchos resultados, incluido un artículo de Fujishige).

Hay otros enfoques disponibles para resolver la minimización submodular. No hay que confundirla con la maximización submodular (o la minimización supermodular), para las que existen algoritmos codiciosos --- porque estos problemas son NP-Hard para aproximar a un factor mejor que $1-1/e$ a menos que se asuma una mayor estructura. De nuevo, en Google encontrarás muchas respuestas sobre el algoritmo codicioso para la maximización submodular.